LeetCode 100. 相同的树(Same Tree):DFS 递归与 BFS 迭代双解法深度解析

原创2026-10-16 15:15:271,368 阅读
文章标签:教程示例工程教育

LeetCode 100. 相同的树(Same Tree):DFS 递归与 BFS 迭代双解法深度解析

本文以 doocs/leetcode 仓库中 0100.Same Tree 题解文档为核心,系统讲解「相同的树」这一二叉树经典判定问题的完整解法:从题目定义与判定规则出发,给出 DFS 递归与 BFS 迭代两套可运行、可直接提交的代码实现(Python、Java、C++、Go、TypeScript、Rust、JavaScript、PHP),并结合仓库源码逐行拆解判定逻辑与复杂度。读完本文,你将掌握二叉树结构等价性判定的标准套路,并能熟练迁移到子树判定、对称树等同类问题。

题目定义:什么样的两棵树才算「相同」

给定两棵二叉树的根节点 p 和 q,编写函数判断它们是否相同。根据 README_EN.md 中的题目描述,两个二叉树相同当且仅当结构上完全一致,且对应位置节点的值相同。这里「结构上完全一致」是一个容易被忽略的要点——不仅两棵树要长得一样,null 子节点的位置也必须一一对应,任何一边多出一个节点都算不同。

判定规则的直观拆解

对任意一对待比较节点,可以归纳为三条互斥的判定规则:

  1. 两个节点均为 null:视为相同,返回 true;
  2. 仅其中一个为 null(或值不同):结构/取值不一致,返回 false;
  3. 两者均非空且值相等:继续递归/迭代比较左子树与右子树。

以上条件全部满足时,两棵树才相同。这一规则同时是 DFS 与 BFS 两种实现的核心逻辑基础。

示例演示

示例 1: p = [1,2,3],q = [1,2,3],输出 true——结构与值完全一致。

![示例1:两棵相同的树](https://raw.gitcode.com/doocs/leetcode/raw/719172c2745794a3fd496df6dc07588f7ccd98d6/lcof2/剑指 Offer II 052. 展平二叉搜索树/images/ex1.jpg?utm_source=gitcode_repo_files)

示例 2: p = [1,2],q = [1,null,2],输出 false——节点 2 在左树中是左孩子,在右树中却是右孩子,结构不同。

![示例2:结构不同的两棵树](https://raw.gitcode.com/doocs/leetcode/raw/719172c2745794a3fd496df6dc07588f7ccd98d6/lcof2/剑指 Offer II 052. 展平二叉搜索树/images/ex2.jpg?utm_source=gitcode_repo_files)

示例 3: p = [1,2,1],q = [1,1,2],输出 false——虽然节点值集合相同,但值 2 和 1 的位置错位,对应位置值不同。

数据范围与约束

根据文档约束(见 README_EN.md 的 Constraints 部分):

  • 两棵树的节点数均在范围 [0, 100] 内,即允许空树(p、q 同时为空应返回 true,仅一棵为空返回 false);
  • 节点值范围 -10^4 <= Node.val <= 10^4。

节点数上限仅为 100,意味着递归深度可控、不会发生栈溢出,DFS 递归方案是安全且推荐的。

方法一:DFS 递归——同步遍历两棵树

算法思想

树由「根节点 + 左右子树」递归定义,因此判断两棵树是否相同,本质上是成对比较两棵树的对应节点。文档(README_EN.md 的 Solution 1 部分)给出的思路是:

  • 若两棵树的根节点都为空,则两树相同;
  • 若有且仅有一个根为空,则两树一定不同;
  • 若两个根都不为空,先比较值:值不同则两树一定不同;值相同则继续判断左子树是否相同且右子树是否相同。

这个判断天然是递归的:isSameTree(p.left, q.left) 与 isSameTree(p.right, q.right) 的结果通过逻辑与(&& / and)组合。值得注意的一个优化细节:仓库中 Python、Java、C++、Go 的实现都先写了 p == q(或 if (p == q) return true)这一短路判断——当两个指针引用同一个对象时直接返回 true,既避免了无意义的递归,也是一种防御性写法。

各语言实现

以下实现均摘自 Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs 以及文档中对应的代码块,与文档完全一致。

Python3(Solution.py):

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p == q:
            return True
        if p is None or q is None or p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Java(Solution.java):

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == q) return true;
        if (p == null || q == null || p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

C++(Solution.cpp):

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == q) return true;
        if (!p || !q || p->val != q->val) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

Go(Solution.go):

func isSameTree(p *TreeNode, q *TreeNode) bool {
	if p == q {
		return true
	}
	if p == nil || q == nil || p.Val != q.Val {
		return false
	}
	return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

TypeScript(Solution.ts):

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

JavaScript(Solution.js):

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

PHP(Solution.php):

class Solution {
    function isSameTree($p, $q) {
        if ($p == null && $q == null) {
            return true;
        }
        if ($p == null || $q == null) {
            return false;
        }
        if ($p->val != $q->val) {
            return false;
        }
        return $this->isSameTree($p->left, $q->left) && $this->isSameTree($p->right, $q->right);
    }
}

Rust(Solution.rs): 由于 Rust 的 TreeNode 用 Option<Rc<RefCell<TreeNode>>> 表示,递归比较需要先通过 borrow() 获取节点的不可变引用再比较值:

impl Solution {
    fn dfs(p: &Option<Rc<RefCell<TreeNode>>>, q: &Option<Rc<RefCell<TreeNode>>>) -> bool {
        if p.is_none() && q.is_none() {
            return true;
        }
        if p.is_none() || q.is_none() {
            return false;
        }
        let r1 = p.as_ref().unwrap().borrow();
        let r2 = q.as_ref().unwrap().borrow();
        r1.val == r2.val && Self::dfs(&r1.left, &r2.left) && Self::dfs(&r1.right, &r2.right)
    }

    pub fn is_same_tree(
        p: Option<Rc<RefCell<TreeNode>>>,
        q: Option<Rc<RefCell<TreeNode>>>,
    ) -> bool {
        Self::dfs(&p, &q)
    }
}

Rust 版本把判定逻辑抽到私有辅助函数 dfs 中,主入口 is_same_tree 只负责转发引用,避免递归时反复移动所有权;同时利用 r1.val == r2.val && ... 的短路求值,在值不相等时立即终止,不再深入子树。

复杂度分析(DFS)

  • 时间复杂度: O(min(m, n)),其中 m、n 分别是两棵树的节点数。两棵树同步前进,一旦在某一对节点发现不一致就立即返回,因此最坏情况也只是完整访问较小的一棵树。
  • 空间复杂度: O(min(m, n)),主要取决于递归调用栈的层数。在链式(退化)二叉树的最坏情况下,递归深度等于节点数;由于两棵树结构一致,深度不会超过节点数较少的那棵树。在题目约束(节点数 ≤ 100)下,递归栈开销完全可接受。

方法二:BFS 迭代——双队列同步层序遍历

算法思想

DFS 方案的代价是消耗系统递归栈。文档(README_EN.md 的 Solution 2 部分)给出的迭代思路是:用两个队列分别承载两棵树的节点,成对取出、成对比较、成对入队,按层序同步推进。

具体比较流程:

  1. 将 p、q 的根节点分别加入两个队列;
  2. 每次从两个队列各取出一个节点 a、b:
    • 若 a.val != b.val,直接返回 false;
    • 比较左右孩子的「存在性」:若一边有左孩子而另一边没有((la && !lb) || (lb && !la)),或右边同理,则结构不同,返回 false;
    • 若左右孩子存在性一致,则把存在的对应孩子成对入队,进入下一轮;
  3. 当两个队列同时为空时,说明所有节点已比较完毕,返回 true。

这里的关键在于「存在性校验 + 成对入队」:空孩子不进入队列,因此队列中永远只有成对的非空节点,天然规避了 null 节点的比较问题。

各语言实现

以下实现摘自 Solution2.py、Solution2.java、Solution2.cpp、Solution2.go、Solution2.ts、Solution2.rs,均与文档代码一致。

Python3(Solution2.py):

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p == q:
            return True
        if p is None or q is None:
            return False
        q1, q2 = deque([p]), deque([q])
        while q1 and q2:
            a, b = q1.popleft(), q2.popleft()
            if a.val != b.val:
                return False
            la, ra = a.left, a.right
            lb, rb = b.left, b.right
            if (la and not lb) or (lb and not la):
                return False
            if (ra and not rb) or (rb and not ra):
                return False
            if la:
                q1.append(la)
                q2.append(lb)
            if ra:
                q1.append(ra)
                q2.append(rb)
        return True

Java(Solution2.java):

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == q) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        Deque<TreeNode> q1 = new ArrayDeque<>();
        Deque<TreeNode> q2 = new ArrayDeque<>();
        q1.offer(p);
        q2.offer(q);
        while (!q1.isEmpty() && !q2.isEmpty()) {
            p = q1.poll();
            q = q2.poll();
            if (p.val != q.val) {
                return false;
            }
            TreeNode la = p.left, ra = p.right;
            TreeNode lb = q.left, rb = q.right;
            if ((la != null && lb == null) || (lb != null && la == null)) {
                return false;
            }
            if ((ra != null && rb == null) || (rb != null && ra == null)) {
                return false;
            }
            if (la != null) {
                q1.offer(la);
                q2.offer(lb);
            }
            if (ra != null) {
                q1.offer(ra);
                q2.offer(rb);
            }
        }
        return true;
    }
}

C++(Solution2.cpp):

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == q) return true;
        if (!p || !q) return false;
        queue<TreeNode*> q1{{p}};
        queue<TreeNode*> q2{{q}};
        while (!q1.empty() && !q2.empty()) {
            p = q1.front();
            q = q2.front();
            if (p->val != q->val) return false;
            q1.pop();
            q2.pop();
            TreeNode *la = p->left, *ra = p->right;
            TreeNode *lb = q->left, *rb = q->right;
            if ((la && !lb) || (lb && !la)) return false;
            if ((ra && !rb) || (rb && !ra)) return false;
            if (la) {
                q1.push(la);
                q2.push(lb);
            }
            if (ra) {
                q1.push(ra);
                q2.push(rb);
            }
        }
        return true;
    }
};

Go(Solution2.go): 使用切片模拟队列,出队通过切片截断 q1[1:] 实现:

func isSameTree(p *TreeNode, q *TreeNode) bool {
	if p == q {
		return true
	}
	if p == nil || q == nil {
		return false
	}
	q1 := []*TreeNode{p}
	q2 := []*TreeNode{q}
	for len(q1) > 0 && len(q2) > 0 {
		p, q = q1[0], q2[0]
		if p.Val != q.Val {
			return false
		}
		q1, q2 = q1[1:], q2[1:]
		la, ra := p.Left, p.Right
		lb, rb := q.Left, q.Right
		if (la != nil && lb == nil) || (lb != nil && la == nil) {
			return false
		}
		if (ra != nil && rb == nil) || (rb != nil && ra == nil) {
			return false
		}
		if la != nil {
			q1 = append(q1, la)
			q2 = append(q2, lb)
		}
		if ra != nil {
			q1 = append(q1, ra)
			q2 = append(q2, rb)
		}
	}
	return true
}

TypeScript(Solution2.ts): 该实现更紧凑,用单个队列成对存放两棵树的节点(先压入 p 的节点再压入 q 的对应节点,每次 shift() 两次取出成对节点):

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    const queue = [];
    p && queue.push(p);
    q && queue.push(q);
    if (queue.length === 1) {
        return false;
    }
    while (queue.length !== 0) {
        const node1 = queue.shift();
        const node2 = queue.shift();
        if (node1.val !== node2.val) {
            return false;
        }
        if (
            (node1.left == null && node2.left != null) ||
            (node1.left != null && node2.left == null)
        ) {
            return false;
        }
        if (
            (node1.right == null && node2.right != null) ||
            (node1.right != null && node2.right == null)
        ) {
            return false;
        }

        if (node1.left != null) {
            queue.push(node1.left);
            queue.push(node2.left);
        }
        if (node1.right != null) {
            queue.push(node1.right);
            queue.push(node2.right);
        }
    }
    return true;
}

注意 TypeScript 版本入口处的处理:p、q 同时为空时队列长度为 0,直接进入 while 后返回 true;仅一个为空时队列长度为 1,提前返回 false。这与其他语言「先判空再入队」的写法等价。

Rust(Solution2.rs): 与 TypeScript 类似的单队列成对策略,借助 VecDeque 实现双端队列,并用 match 模式匹配对左右孩子的存在性进行分支处理:

impl Solution {
    pub fn is_same_tree(
        mut p: Option<Rc<RefCell<TreeNode>>>,
        mut q: Option<Rc<RefCell<TreeNode>>>,
    ) -> bool {
        let mut queue = VecDeque::new();
        if p.is_some() {
            queue.push_back(p.take());
        }
        if q.is_some() {
            queue.push_back(q.take());
        }
        if queue.len() == 1 {
            return false;
        }
        while queue.len() != 0 {
            if let (Some(mut node1), Some(mut node2)) = (queue.pop_front(), queue.pop_front()) {
                let mut node1 = node1.as_mut().unwrap().borrow_mut();
                let mut node2 = node2.as_mut().unwrap().borrow_mut();
                if node1.val != node2.val {
                    return false;
                }
                match (node1.left.is_some(), node2.left.is_some()) {
                    (false, false) => {}
                    (true, true) => {
                        queue.push_back(node1.left.take());
                        queue.push_back(node2.left.take());
                    }
                    (_, _) => {
                        return false;
                    }
                }
                match (node1.right.is_some(), node2.right.is_some()) {
                    (false, false) => {}
                    (true, true) => {
                        queue.push_back(node1.right.take());
                        queue.push_back(node2.right.take());
                    }
                    (_, _) => {
                        return false;
                    }
                }
            }
        }
        true
    }
}

复杂度分析(BFS)

  • 时间复杂度: O(min(m, n))。与 DFS 相同,两棵树成对同步遍历,任一时刻发现不一致立即返回。
  • 空间复杂度: O(min(m, n))。空间取决于队列中的元素个数;同一层入队的节点对数量不会超过较小树的节点总数。相比 DFS 的递归栈,BFS 在极端链式树上不会产生深栈,但队列在满二叉树的最宽层也会达到 O(n) 量级,两者渐近复杂度一致。

两种方法对比与选型建议

维度 DFS 递归 BFS 迭代
遍历顺序 深度优先(先根,再左/右子树) 广度优先(按层成对比较)
数据结构 系统调用栈 显式队列(双队列或单队列成对存放)
时间复杂度 O(min(m, n)) O(min(m, n))
空间复杂度 O(min(m, n))(递归栈) O(min(m, n))(队列)
提前终止 值不等/结构不等时立即返回 同左
适合场景 实现简洁、易读;节点规模不大时首选 避免递归深度问题;面试考察迭代写法时

选型建议: 在本题约束(节点数 ≤ 100)下两种方案均无性能风险,优先推荐 DFS 递归——代码更短、语义更贴合「树是递归结构」的本质;如果面试官要求写出非递归版本,或树可能极深(如退化链表形态且节点数很大),则采用 BFS 迭代更稳妥。

仓库中的代码组织:从题解文档到可提交文件

在 doocs/leetcode 仓库中,本题目录 solution/0100-0199/0100.Same Tree 采用「文档 + 独立源码文件」双轨组织:

  • 题解文档: README.md(中文)与 README_EN.md(英文),包含题目描述、示例图与完整解法说明;
  • 解法一源码: Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.js、Solution.php、Solution.rs——对应 DFS 递归实现,文件内容与文档代码块完全一致;
  • 解法二源码: Solution2.py、Solution2.java、Solution2.cpp、Solution2.go、Solution2.ts、Solution2.rs——对应 BFS 迭代实现;
  • 示例图: images/ex1.jpg、images/ex2.jpg、images/ex3.jpg 展示了三个输入输出示例的树形结构。

这种「一题多解、一解多语言」的布局意味着:无论你使用哪种语言准备面试,都可以直接在对应 Solution*. 文件中找到可直接提交的完整代码,并以文档中的复杂度分析作为复习要点。

思维拓展:从「相同树」到同类树问题

「相同的树」的判定框架可以顺滑迁移到一批经典二叉树问题,理解其判定规则后能事半功倍:

  • 判断一棵树是否为另一棵树的子树(Subtree of Another Tree):对主树的每个节点调用「两树相同」判断,即可转化为本问题的组合应用;
  • 对称二叉树(Symmetric Tree):将一棵树的左子树与右子树互为镜像比较,比较逻辑与本问题高度相似,只是孩子配对方向相反(左对右、右对左);
  • 判断两棵树结构是否一致但值可不同:只需把「值比较」去掉,保留结构与存在性判断,即可衍生出「同构(isomorphic)树」变体。

掌握本文的成对比较思想(p、q 同步前进 + 空值处理 + 短路返回),就掌握了这一系列树问题的最小公共核心。

小结

LeetCode 100. 相同的树是一道「高频且基础」的二叉树入门题,考察的是对递归/迭代遍历的掌握与边界条件(空节点)处理。doocs/leetcode 仓库为本题提供了两种解法、八种语言的完整实现:DFS 递归版代码简洁、语义直观;BFS 迭代版避免了调用栈依赖,适合考察非递归写法的场景。两者时间复杂度均为 O(min(m, n)),空间复杂度均为 O(min(m, n))。建议对照 Solution.py 与 Solution2.py 各默写一遍,再尝试迁移到子树判定与对称树问题,即可彻底吃透这一类树的等价性判定。

登录后查看全文
leetcode