100. 相同的树 🟩

题目

LeetCode 简单

题目

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例：
输入：p = [1,2,3], q = [1,2,3]
输出：true

输入：p = [1,2,1], q = [1,1,2]
输出：false

题解

方法：递归

DFS 深度优先 递归

时间复杂度：O(min(m,n))
时间复杂度：O(min(m,n))

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  console.log('p', p?.val, 'q', q?.val)

  if (!p && !q) return true
  if (
    p &&
    q &&
    p.val === q.val &&
    isSameTree(p.left, q.left) &&
    isSameTree(p.right, q.right)
  )
    return true
  return false
}

const p = new Tree([1, 2, 3]),
  q = new Tree([1, 2, 3])
const p1 = new Tree([1, 2, 3, 4, 5, 6, 7]),
  q1 = new Tree([1, 2, 3, 4, 5, 7, 8])

console.log('🌰', isSameTree(p.root, q.root))
console.log('🌰', isSameTree(p1.root, q1.root))

方法：迭代

在 JS 中，既可以用栈（pop() 弹出尾部，做深度优先遍历 DFS），也可以用队列（shift() 弹出头部，做广度优先遍历 BFS）。两者逻辑在这道题里完全通用。

时间复杂度：O(min(m,n))
时间复杂度：O(min(m,n))

// 1. 定义二叉树节点
class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

// ==========================================
// 核心算法：相同的树 (迭代法)
// ==========================================
var isSameTree = function (p, q) {
  // 使用一个栈来存储需要比较的“节点对”
  // 初始状态把两棵树的根节点成对放进去
  const stack = [[p, q]]

  while (stack.length > 0) {
    console.log(
      'stack',
      JSON.stringify(
        stack.map(([nodeP, nodeQ]) => [
          nodeP ? nodeP.val : null,
          nodeQ ? nodeQ.val : null,
        ]),
      ),
    )

    // 每次弹出一对节点进行同步比较 (DFS 深度优先)
    const [nodeP, nodeQ] = stack.pop()

    // 1. 如果两个节点都为空，说明这一分支结构相同且到底了，放行
    if (nodeP === null && nodeQ === null) {
      continue
    }

    // 2. 如果其中一个为空，另一个不为空，说明结构不同，直接判死刑
    if (nodeP === null || nodeQ === null) {
      return false
    }

    // 3. 两个都不为空，但值不同，判死刑
    if (nodeP.val !== nodeQ.val) {
      return false
    }

    // 走到这里说明当前节点长得一模一样
    // 把它们的左右子节点分别配对，压入栈中等待后续审查
    // ⚠️ 注意：一定要 p 的左边配 q 的左边，p 的右边配 q 的右边！
    stack.push([nodeP.right, nodeQ.right])
    stack.push([nodeP.left, nodeQ.left])
  }

  // 栈都被清空了，所有的节点对都经受住了考验
  return true
}

// --- 运行测试 ---

// 树 A: [1, 2, 3]
const treeA = new TreeNode(1, new TreeNode(2), new TreeNode(3))
// 树 B: [1, 2, 3]
const treeB = new TreeNode(1, new TreeNode(2), new TreeNode(3))
// 树 C: [1, null, 2] (结构不同)
const treeC = new TreeNode(1, null, new TreeNode(2))

console.log(
  '🌰 TreeA 和 TreeB 是否相同？ (预期: true) ->',
  isSameTree(treeA, treeB),
)
console.log('-----------------------------')
console.log(
  '🌰 TreeA 和 TreeC 是否相同？ (预期: false)->',
  isSameTree(treeA, treeC),
)

执行结果

stack [[1,1]]
stack [[3,3],[2,2]]
stack [[3,3],[null,null],[null,null]]
stack [[3,3],[null,null]]
stack [[3,3]]
stack [[null,null],[null,null]]
stack [[null,null]]
🌰 TreeA 和 TreeB 是否相同？ (预期: true) -> true
-----------------------------
stack [[1,1]]
stack [[3,2],[2,null]]
🌰 TreeA 和 TreeC 是否相同？ (预期: false)-> false

本页目录