解题步骤

  1. 分：获取两个树的左子树和右子树
  2. 解：递归地判断两个树的左子树是否相同，右子树是否相同
  3. 合：将上述结果合并，如果根节点的值相同，树就相同

通过分而治之思想实现

  • 时间复杂度：O (n)

  • 空间复杂度：O (h)

    1. function isSameTree(p, q) {
    2.   if (!p && !q) return true;
    4.   if (!p || !q) return false;
    6.   if (p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right)) {
    7.       return true;
    8.   }
    10.   return false;
    11. }

代码中利用递归遍历了树的所有节点，所以时间复杂度是 O (n) ，而空间复杂度是 O (h) h 是树的高度，因为存在调用堆栈占据了空间。