LeetCode 题解工作台
相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。 示例 1： 输入： p = [1,2,3], q = [1,2,3] 输出： true 示例 2： 输入： p = [1,2], q = [1,null,2…
4
题型
8
代码语言
3
相关题
当前训练重点
简单 · 二分·树·traversal
答案摘要
我们可以使用 DFS 递归的方法来解决这个问题。 首先判断两个二叉树的根节点是否相同，如果两个根节点都为空，则两个二叉树相同，如果两个根节点中有且只有一个为空，则两个二叉树一定不同。如果两个根节点都不为空，则判断它们的值是否相同，如果不相同则两个二叉树一定不同，如果相同，则分别判断两个二叉树的左子树是否相同以及右子树是否相同。当以上所有条件都满足时，两个二叉树才相同。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3] 输出：true
示例 2：
输入：p = [1,2], q = [1,null,2] 输出：false
示例 3：
输入：p = [1,2,1], q = [1,1,2] 输出：false
提示：
- 两棵树上的节点数目都在范围
[0, 100]内 -104 <= Node.val <= 104
解题思路
方法一：DFS
我们可以使用 DFS 递归的方法来解决这个问题。
首先判断两个二叉树的根节点是否相同，如果两个根节点都为空，则两个二叉树相同，如果两个根节点中有且只有一个为空，则两个二叉树一定不同。如果两个根节点都不为空，则判断它们的值是否相同，如果不相同则两个二叉树一定不同，如果相同，则分别判断两个二叉树的左子树是否相同以及右子树是否相同。当以上所有条件都满足时，两个二叉树才相同。
时间复杂度 ，空间复杂度 。其中 和 分别是两个二叉树的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的节点个数。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
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)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n), where n is the total number of nodes, because every node is visited once during DFS or BFS. Space complexity is O(h) for DFS recursion or stack, where h is tree height, and O(w) for BFS queue, where w is maximum tree width. These complexities align with the chosen traversal method and the need to track corresponding nodes. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you account for null nodes when comparing two trees?
- question_mark
Can you implement both DFS and BFS to validate the trees efficiently?
- question_mark
Will you handle early termination when a mismatch is detected to optimize runtime?
常见陷阱
外企场景- error
Failing to check for null nodes on only one side leading to incorrect true result.
- error
Comparing node values without ensuring structural alignment can return false negatives.
- error
Using BFS without properly enqueuing null children may skip necessary comparisons.
进阶变体
外企场景- arrow_right_alt
Check if one tree is a subtree of another while preserving structure and values.
- arrow_right_alt
Determine if two n-ary trees are identical using modified traversal logic.
- arrow_right_alt
Compare two trees to see if they are mirrors of each other rather than identical.