相同的树 (opens new window)

• 难度：Easy
• 标签：DFS 递归

刷题思路

• [x] DFS递归
• [x] DFS迭代

方法 1 递归

• 复杂度：
  • 时间 O(min(m, n))
  • 空间 O(min(m, n))
• 结果：
  • 执行用时：76 ms, 在所有 JavaScript 提交中击败了85.48%的用户
  • 内存消耗：38.4 MB, 在所有 JavaScript 提交中击败了5.00%的用户

var isSameTree = function(p, q) {
    if (p === q) return true
    if (!p || !q) return false
    return p.val===q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
};

方法 2

• 思路: 创建栈，塞入原始数据，在不断推进的过程中做判断，能够完全完成为 true.
• 复杂度分析:
  • 时间: O(min(m, n))
  • 空间: O(min(m, n))
• 结果：
  • 执行用时：84 ms, 在所有 JavaScript 提交中击败了64.15%的用户
  • 内存消耗：38.5 MB, 在所有 JavaScript 提交中击败了6.07%的用户

var isSameTree = function(p, q) {
    const stack = [[p, q]]
    while (stack.length > 0) {
        const [a, b] = stack.pop()
        if (!isEqual(a, b)) return false
        if (a && b) {
            stack.push([a.right, b.right])
            stack.push([a.left, b.left])
        }
    }
    return true
};

function isEqual (a, b) {
    if (a === b) return true
    if (!a || !b) return false
    if (a.val !== b.val) return false
    return true
}

JS刷题记录 Leetcode-js (opens new window) 每周都会更新刷题心得或者题解, 你的点赞或 star 都将助力我产出更好内容~