LeetCode 100简单二叉树 · 递归

相同的树图解题解

两棵树结构和值完全相同？递归让每个节点自己回答这个问题。

两张家谱对照看是否一模一样：站在根节点，先比这两人名字，不同立刻否；相同再让左子树和右子树各自去对照——同一套规则递归铺下去。遇到两边都空说明这支对上了，一空一非说明结构不同，任一层不过就整体不同。每个节点只做一次比较，O(n) 走完。

这道题到底在问什么

给定两棵二叉树的根节点 p 和 q，若它们结构相同且对应节点值相同，返回 true，否则 false。

输入: p=[1,2,3,4,5,..], q=[1,2,3,4,5,..]
输出: true

最优解：一步一步想明白

3把判断「两棵树相同」拆成同步递归：每一步同时看两棵树的同一个位置。当前两节点值相同，且它们的左子树相同，且它们的右子树相同——三个条件都满足，才算这一支相同。下面用两棵真的一样的树，逐对走一遍。
4左=p 右=q，从两个根开始同步递归先看清布局：把两棵树并排画——左半边是树 p、右半边是树 q（顶上的「相同?」只是个标记，不参与比较）。接下来从两个根节点出发，同位置一对一对地比，看看它们是不是真的完全一样。
5compare A[1] vs B[1] → 看值是否相同同步递归来到这一对：左树的 1 对上右树同一位置的 1。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
61 == 1 ✓ → 递归左对左、右对右1 和 1 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
7compare A[2] vs B[2] → 看值是否相同同步递归来到这一对：左树的 2 对上右树同一位置的 2。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
82 == 2 ✓ → 递归左对左、右对右2 和 2 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
9compare A[4] vs B[4] → 看值是否相同同步递归来到这一对：左树的 4 对上右树同一位置的 4。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
104 == 4 ✓ → 递归左对左、右对右4 和 4 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
11compare A[8] vs B[8] → 看值是否相同同步递归来到这一对：左树的 8 对上右树同一位置的 8。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
128 == 8 ✓ → 递归左对左、右对右8 和 8 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
138 的左孩子两侧都空 → 这一支相同，回 true顺着节点 8 往它的左孩子递归，发现两棵树这个位置都是空的。空 vs 空正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
148 的右孩子两侧都空 → 这一支相同，回 true顺着节点 8 往它的右孩子递归，发现两棵树这个位置都是空的。空 vs 空正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
154 的右孩子两侧都空 → 这一支相同，回 true顺着节点 4 往它的右孩子递归，发现两棵树这个位置都是空的。空 vs 空正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
16compare A[5] vs B[5] → 看值是否相同同步递归来到这一对：左树的 5 对上右树同一位置的 5。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
175 == 5 ✓ → 递归左对左、右对右5 和 5 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
185 的左孩子两侧都空 → 这一支相同，回 true顺着节点 5 往它的左孩子递归，发现两棵树这个位置都是空的。空 vs 空正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
195 的右孩子两侧都空 → 这一支相同，回 true顺着节点 5 往它的右孩子递归，发现两棵树这个位置都是空的。空 vs 空正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
20compare A[3] vs B[3] → 看值是否相同同步递归来到这一对：左树的 3 对上右树同一位置的 3。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
213 == 3 ✓ → 递归左对左、右对右3 和 3 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
22compare A[6] vs B[6] → 看值是否相同同步递归来到这一对：左树的 6 对上右树同一位置的 6。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
236 == 6 ✓ → 递归左对左、右对右6 和 6 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
24compare A[9] vs B[9] → 看值是否相同同步递归来到这一对：左树的 9 对上右树同一位置的 9。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
259 == 9 ✓ → 递归左对左、右对右9 和 9 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
269 的左孩子两侧都空 → 这一支相同，回 true顺着节点 9 往它的左孩子递归，发现两棵树这个位置都是空的。空 vs 空正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
279 的右孩子两侧都空 → 这一支相同，回 true顺着节点 9 往它的右孩子递归，发现两棵树这个位置都是空的。空 vs 空正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
286 的右孩子两侧都空 → 这一支相同，回 true顺着节点 6 往它的右孩子递归，发现两棵树这个位置都是空的。空 vs 空正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
29compare A[7] vs B[7] → 看值是否相同同步递归来到这一对：左树的 7 对上右树同一位置的 7。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
307 == 7 ✓ → 递归左对左、右对右7 和 7 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
317 的左孩子两侧都空 → 这一支相同，回 true顺着节点 7 往它的左孩子递归，发现两棵树这个位置都是空的。空 vs 空正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
327 的右孩子两侧都空 → 这一支相同，回 true顺着节点 7 往它的右孩子递归，发现两棵树这个位置都是空的。空 vs 空正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
33all pairs equal → return true所有同位置的对都比完了：每一对的值都相等，所有空位也都「空对空」对上。三个条件（值同 + 左子树同 + 右子树同）一路成立，递归层层回传 true——两棵树相同，答案 = true。

⚠️ 容易写错的地方

✗ 错：只比节点值、不管结构

✓ 对：同位置「空 vs 空」也要对上

结构不同就算值序一样也不相同

✗ 错：漏写「一空一非空 → false」

✓ 对：两个 null 出口要分开判

少这一行会在某侧为空时空指针出错

✗ 错：左右子树用「或」连接

✓ 对：必须是「与」：左右都相同才相同

用「或」会把只对了一半的判成相同

完整代码（Java / Python / C++）

Java

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;     // 都空：这一支一致
        if (p == null || q == null) return false;    // 一空一非空：不同
        if (p.val != q.val) return false;            // 值不同：不同
        return isSameTree(p.left,  q.left)           // 左对左
            && isSameTree(p.right, q.right);         // 右对右，都同才同
    }
}

Python

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p is None and q is None:      # 都空：这一支一致
            return True
        if p is None or q is None:       # 一空一非空：不同
            return False
        if p.val != q.val:               # 值不同：不同
            return False
        return (self.isSameTree(p.left,  q.left)
                and self.isSameTree(p.right, q.right))

C++

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) return true;       // 都空：这一支一致
        if (!p || !q) return false;      // 一空一非空：不同
        if (p->val != q->val) return false;  // 值不同：不同
        return isSameTree(p->left,  q->left)
            && isSameTree(p->right, q->right);  // 左对左、右对右
    }
};

复杂度

时间

O(n)

n=较小树的节点数；最多把每对节点比一次

空间

O(h)

递归栈深 = 树高 h；最坏(链)O(n)，平衡 O(log n)

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着相同的树的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

这道题为什么用「递归」，换最直接的暴力解会差在哪？+

递归抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。

时间复杂度为什么是 undefined？怎么推出来的？+

按上文复杂度小节的推导，时间复杂度为 undefined。

想听吴师兄把这道题讲给你听？

文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把相同的树一步步讲透（全站已上线 905 份讲透，持续扩充），卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。

了解年卡方案 →先去动画页看完整样板 →

把这道题真正拿下

看动画图解 →相同的树交互动画,逐步看清每一步怎么走

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

LeetCode 100简单二叉树 · 递归

相同的树图解题解

两棵树结构和值完全相同？递归让每个节点自己回答这个问题。

这道题到底在问什么

给定两棵二叉树的根节点 p 和 q，若它们结构相同且对应节点值相同，返回 true，否则 false。

输入: p=[1,2,3,4,5,..], q=[1,2,3,4,5,..]
输出: true

最优解：一步一步想明白

3把判断「两棵树相同」拆成同步递归：每一步同时看两棵树的同一个位置。当前两节点值相同，且它们的左子树相同，且它们的右子树相同——三个条件都满足，才算这一支相同。下面用两棵真的一样的树，逐对走一遍。
4左=p 右=q，从两个根开始同步递归先看清布局：把两棵树并排画——左半边是树 p、右半边是树 q（顶上的「相同?」只是个标记，不参与比较）。接下来从两个根节点出发，同位置一对一对地比，看看它们是不是真的完全一样。
5compare A[1] vs B[1] → 看值是否相同同步递归来到这一对：左树的 1 对上右树同一位置的 1。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
61 == 1 ✓ → 递归左对左、右对右1 和 1 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
7compare A[2] vs B[2] → 看值是否相同同步递归来到这一对：左树的 2 对上右树同一位置的 2。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
82 == 2 ✓ → 递归左对左、右对右2 和 2 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
9compare A[4] vs B[4] → 看值是否相同同步递归来到这一对：左树的 4 对上右树同一位置的 4。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
104 == 4 ✓ → 递归左对左、右对右4 和 4 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
11compare A[8] vs B[8] → 看值是否相同同步递归来到这一对：左树的 8 对上右树同一位置的 8。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
128 == 8 ✓ → 递归左对左、右对右8 和 8 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
138 的左孩子两侧都空 → 这一支相同，回 true顺着节点 8 往它的左孩子递归，发现两棵树这个位置都是空的。空 vs 空正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
148 的右孩子两侧都空 → 这一支相同，回 true顺着节点 8 往它的右孩子递归，发现两棵树这个位置都是空的。空 vs 空正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
154 的右孩子两侧都空 → 这一支相同，回 true顺着节点 4 往它的右孩子递归，发现两棵树这个位置都是空的。空 vs 空正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
16compare A[5] vs B[5] → 看值是否相同同步递归来到这一对：左树的 5 对上右树同一位置的 5。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
175 == 5 ✓ → 递归左对左、右对右5 和 5 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
185 的左孩子两侧都空 → 这一支相同，回 true顺着节点 5 往它的左孩子递归，发现两棵树这个位置都是空的。空 vs 空正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
195 的右孩子两侧都空 → 这一支相同，回 true顺着节点 5 往它的右孩子递归，发现两棵树这个位置都是空的。空 vs 空正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
20compare A[3] vs B[3] → 看值是否相同同步递归来到这一对：左树的 3 对上右树同一位置的 3。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
213 == 3 ✓ → 递归左对左、右对右3 和 3 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
22compare A[6] vs B[6] → 看值是否相同同步递归来到这一对：左树的 6 对上右树同一位置的 6。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
236 == 6 ✓ → 递归左对左、右对右6 和 6 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
24compare A[9] vs B[9] → 看值是否相同同步递归来到这一对：左树的 9 对上右树同一位置的 9。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
259 == 9 ✓ → 递归左对左、右对右9 和 9 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
269 的左孩子两侧都空 → 这一支相同，回 true顺着节点 9 往它的左孩子递归，发现两棵树这个位置都是空的。空 vs 空正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
279 的右孩子两侧都空 → 这一支相同，回 true顺着节点 9 往它的右孩子递归，发现两棵树这个位置都是空的。空 vs 空正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
286 的右孩子两侧都空 → 这一支相同，回 true顺着节点 6 往它的右孩子递归，发现两棵树这个位置都是空的。空 vs 空正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
29compare A[7] vs B[7] → 看值是否相同同步递归来到这一对：左树的 7 对上右树同一位置的 7。两棵树要「相同」，先决条件就是每一对同位置的节点值都相等，所以这一帧先把它俩同时点亮，准备比对。
307 == 7 ✓ → 递归左对左、右对右7 和 7 值相等 ✓，这一对节点本身过关，标成绿色(已相同)。但「相同的树」不只看当前这一对——还得左子树对左子树、右子树对右子树都相同，于是递归继续往下比。
317 的左孩子两侧都空 → 这一支相同，回 true顺着节点 7 往它的左孩子递归，发现两棵树这个位置都是空的。空 vs 空正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
327 的右孩子两侧都空 → 这一支相同，回 true顺着节点 7 往它的右孩子递归，发现两棵树这个位置都是空的。空 vs 空正是递归出口——这一支比到底、完全一致，返回 true 往上回传。
33all pairs equal → return true所有同位置的对都比完了：每一对的值都相等，所有空位也都「空对空」对上。三个条件（值同 + 左子树同 + 右子树同）一路成立，递归层层回传 true——两棵树相同，答案 = true。

⚠️ 容易写错的地方

✗ 错：只比节点值、不管结构

✓ 对：同位置「空 vs 空」也要对上

结构不同就算值序一样也不相同

✗ 错：漏写「一空一非空 → false」

✓ 对：两个 null 出口要分开判

少这一行会在某侧为空时空指针出错

✗ 错：左右子树用「或」连接

✓ 对：必须是「与」：左右都相同才相同

用「或」会把只对了一半的判成相同

完整代码（Java / Python / C++）

Java

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;     // 都空：这一支一致
        if (p == null || q == null) return false;    // 一空一非空：不同
        if (p.val != q.val) return false;            // 值不同：不同
        return isSameTree(p.left,  q.left)           // 左对左
            && isSameTree(p.right, q.right);         // 右对右，都同才同
    }
}

Python

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p is None and q is None:      # 都空：这一支一致
            return True
        if p is None or q is None:       # 一空一非空：不同
            return False
        if p.val != q.val:               # 值不同：不同
            return False
        return (self.isSameTree(p.left,  q.left)
                and self.isSameTree(p.right, q.right))

C++

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) return true;       // 都空：这一支一致
        if (!p || !q) return false;      // 一空一非空：不同
        if (p->val != q->val) return false;  // 值不同：不同
        return isSameTree(p->left,  q->left)
            && isSameTree(p->right, q->right);  // 左对左、右对右
    }
};

复杂度

时间

O(n)

n=较小树的节点数；最多把每对节点比一次

空间

O(h)

递归栈深 = 树高 h；最坏(链)O(n)，平衡 O(log n)

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着相同的树的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

这道题为什么用「递归」，换最直接的暴力解会差在哪？+

时间复杂度为什么是 undefined？怎么推出来的？+

按上文复杂度小节的推导，时间复杂度为 undefined。

想听吴师兄把这道题讲给你听？

了解年卡方案 →先去动画页看完整样板 →

把这道题真正拿下

看动画图解 →相同的树交互动画,逐步看清每一步怎么走

相同的树 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Java / Python / C++）

Java

Python

C++

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

相同的树 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Java / Python / C++）

Java

Python

C++

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

相同的树图解题解

相同的树图解题解