作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给定两个二叉树的根节点 p 和 q，编写一个函数来检测这两棵树是否相同。如果两棵树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例
示例 1
输入：p = [1,2,3], q = [1,2,3]
输出：True
示例 2
输入：p = [1,2], q = [1,null,2]
输出：False
方法一：递归比较
解题步骤
- 基本情况：如果两个节点都是
None，返回True。如果一个是None另一个不是，返回False。 - 值比较：如果当前两个节点的值不同，返回
False。 - 递归比较：递归比较左子树和右子树。
Python 示例
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def isSameTree(p, q): """ 递归比较两棵树是否相同 :param p: TreeNode, 第一棵树的根节点 :param q: TreeNode, 第二棵树的根节点 :return: bool, 两棵树是否相同 """ if not p and not q: return True if not p or not q: return False if p.val != q.val: return False return isSameTree(p.left, q.left) and isSameTree(p.right, q.right) # 示例调用 p = TreeNode(1, TreeNode(2), TreeNode(3)) q = TreeNode(1, TreeNode(2), TreeNode(3)) print(isSameTree(p, q)) # 输出: True
算法分析
- 时间复杂度：(O(n))，其中 (n) 是树中节点的数量，因为需要访问树中的每一个节点。
- 空间复杂度：(O(h))，其中 (h) 是树的高度，空间消耗来自递归的栈空间。
ASCII 图解过程
[开始比较根节点] [1 == 1] -> True |---[左子树比较] | [2 == 2] -> True | |--[左子树比较] -> [null == null] -> True | |--[右子树比较] -> [null == null] -> True | |---[右子树比较] [3 == 3] -> True |--[左子树比较] -> [null == null] -> True |--[右子树比较] -> [null == null] -> True [树结构完全匹配] -> True
方法二：迭代使用队列
解题步骤
- 初始化队列：将根节点的对 (p, q) 加入队列。
- 迭代处理：从队列中取出节点对，比较这两个节点。如果不相同，则返回
False。如果相同，将他们的左孩子和右孩子按对加入队列。 - 重复：重复这个过程，直到队列为空。
Python 示例
from collections import deque def isSameTree(p, q): """ 迭代使用队列比较两棵树是否相同 :param p: TreeNode, 第一棵树的根节点 :param q: TreeNode, 第二棵树的根节点 :return: bool, 两棵树是否相同 """ queue = deque([(p, q)]) while queue: p, q = queue.popleft() if not p and not q: continue if not p or not q: return False if p.val != q.val: return False queue.append((p.left, q.left)) queue.append((p.right, q.right)) return True # 示例调用 p = TreeNode(1, TreeNode(2), TreeNode(3)) q = TreeNode(1, TreeNode(2), TreeNode(3)) print(isSameTree(p, q)) # 输出: True
算法分析
- 时间复杂度：(O(n))
- 空间复杂度：(O(n))，在最坏的情况下，如果树完全不平衡，队列可能需要存储所有节点。
ASCII 图解过程
[初始化队列] -> [(1, 1)] |--[比较节点 1 和 1] -> True | |--[加入子节点对] -> [(2, 2), (3, 3)] | |--[比较节点 2 和 2] -> True | |--[子节点都是 null，跳过] | |--[比较节点 3 和 3] -> True |--[子节点都是 null，跳过] [队列空，结束] -> True
方法三：DFS 使用栈
解题步骤
- 使用栈模拟递归：将节点对压入栈中。
- 迭代比较：从栈中弹出节点对，进行比较。如果不相同，则返回
False。如果相同，将他们的左孩子和右孩子按对压入栈。 - 重复：直到栈为空。
Python 示例
def isSameTree(p, q): """ 使用栈实现深度优先搜索比较两棵树是否相同 :param p: TreeNode, 第一棵树的根节点 :param q: TreeNode, 第二棵树的根节点 :return: bool, 两棵树是否相同 """ stack = [(p, q)] while stack: p, q = stack.pop() if not p and not q: continue if not p or not q or p.val != q.val: return False stack.append((p.right, q.right)) stack.append((p.left, q.left)) return True # 示例调用 p = TreeNode(1, TreeNode(2), TreeNode(3)) q = TreeNode(1, TreeNode(2), TreeNode(3)) print(isSameTree(p, q)) # 输出: True
算法分析
- 时间复杂度：(O(n))
- 空间复杂度：(O(h))，其中 (h) 是树的高度，因为栈的最大深度由树的高度决定。
ASCII 图解过程
[初始化栈] -> [(1, 1)] |--[弹出节点 1 和 1] -> True | |--[压入子节点对] -> [(3, 3), (2, 2)] | |--[弹出节点 2 和 2] -> True | |--[子节点都是 null，跳过] | |--[弹出节点 3 和 3] -> True |--[子节点都是 null，跳过] [栈空，结束] -> True
总结
这些方法提供了不同的方式来解决确定两棵树是否相同的问题。递归方法直观且易于实现，而迭代方法则在某些情况下可以提供更好的空间效率。选择哪种方法取决于具体情况和个人偏好。这些方法不仅可以应用于算法和数据结构的学习，还可以在实际开发中用于测试框架中验证复杂算法的输出结果或进行自动化测试。
欢迎关注微信公众号 数据分析螺丝钉
