DEV Community
·
Leetcode - 100. 同树
💡
原文英文，约600词，阅读约需2分钟。
📝
内容提要
“同树”问题是经典面试题，检查两个二叉树的结构和节点值是否相同。提供三种解决方案：递归（DFS）、队列迭代（BFS）和栈迭代（DFS），时间复杂度均为O(n)，空间复杂度分别为O(h)和O(n)。选择方法取决于树的深度和代码可读性。
🎯
关键要点
-
同树问题是经典面试题，检查两个二叉树的结构和节点值是否相同。
-
提供三种解决方案：递归（DFS）、队列迭代（BFS）和栈迭代（DFS）。
-
递归方法逻辑：如果两个节点都为null，返回true；如果一个为null或值不匹配，返回false；递归检查左右子节点。
-
递归方法的时间复杂度为O(n)，空间复杂度为O(h)。
-
队列迭代方法使用两个队列逐层处理两个树，逻辑是比较节点并入队其子节点。
-
队列迭代方法的时间复杂度为O(n)，空间复杂度为O(n)。
-
栈迭代方法模拟递归，使用栈存储节点对，逻辑是比较节点并推入其子节点。
-
栈迭代方法的时间复杂度为O(n)，空间复杂度为O(h)。
-
比较表显示三种方法的时间复杂度均为O(n)，空间复杂度分别为O(h)和O(n)，可读性和栈溢出风险各有不同。
-
选择方法取决于树的深度和代码可读性。
❓
延伸问答
同树问题的主要目标是什么？
同树问题的目标是检查两个二叉树的结构是否相同以及节点值是否相等。
有哪些方法可以解决同树问题？
解决同树问题的方法有递归（DFS）、队列迭代（BFS）和栈迭代（DFS）。
递归方法的时间复杂度和空间复杂度分别是多少？
递归方法的时间复杂度为O(n)，空间复杂度为O(h)。
队列迭代方法的逻辑是什么？
队列迭代方法使用两个队列逐层处理两个树，比较节点并入队其子节点。
选择哪种方法取决于什么因素？
选择方法取决于树的深度和代码的可读性。
栈迭代方法与递归方法的空间复杂度有什么相似之处？
栈迭代方法的空间复杂度与递归方法相似，均为O(h)。
➡️
