zhangdizhangdi

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))

ts
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))

方法：广度优先【todo⌛️】

BFS