LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树

简介: LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化:企业实战案例

python源码解读

程序员必备的数学知识与应用

备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

题目描述

给定两个二叉树的根节点 pq,编写一个函数来检测这两棵树是否相同。如果两棵树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

示例

示例 1

输入:p = [1,2,3], q = [1,2,3]

输出:True

示例 2

输入:p = [1,2], q = [1,null,2]

输出:False


方法一:递归比较

解题步骤
  1. 基本情况:如果两个节点都是 None,返回 True。如果一个是 None 另一个不是,返回 False
  2. 值比较:如果当前两个节点的值不同,返回 False
  3. 递归比较:递归比较左子树和右子树。
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

方法二:迭代使用队列

解题步骤
  1. 初始化队列:将根节点的对 (p, q) 加入队列。
  2. 迭代处理:从队列中取出节点对,比较这两个节点。如果不相同,则返回 False。如果相同,将他们的左孩子和右孩子按对加入队列。
  3. 重复:重复这个过程,直到队列为空。
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 使用栈

解题步骤
  1. 使用栈模拟递归:将节点对压入栈中。
  2. 迭代比较:从栈中弹出节点对,进行比较。如果不相同,则返回 False。如果相同,将他们的左孩子和右孩子按对压入栈。
  3. 重复:直到栈为空。
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

总结

这些方法提供了不同的方式来解决确定两棵树是否相同的问题。递归方法直观且易于实现,而迭代方法则在某些情况下可以提供更好的空间效率。选择哪种方法取决于具体情况和个人偏好。这些方法不仅可以应用于算法和数据结构的学习,还可以在实际开发中用于测试框架中验证复杂算法的输出结果或进行自动化测试。


欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
23天前
|
存储 算法 Java
Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。
【6月更文挑战第21天】Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。二叉树遍历通过访问根、左、右子节点实现。DFS采用递归遍历图的节点,而BFS利用队列按层次访问。以下是简化的代码片段:[Java代码略]
22 4
|
23天前
|
存储 算法 程序员
数据结构与算法===递归
数据结构与算法===递归
|
9天前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
11 3
|
20天前
|
算法 Java
Java数据结构与算法:图算法之深度优先搜索(DFS)
Java数据结构与算法:图算法之深度优先搜索(DFS)
|
22天前
|
算法 索引
DFS算法及应用(二)
回溯:回溯就是DFS的一种,在搜索探索过程中寻找问题的解,当发现不满足求解条件时,就回溯返回,尝试其他路径。
|
22天前
|
算法
DFS算法及应用(一)
DFS(深度优先搜索)是一种图遍历算法,常用于解决穷举问题,如全排列、迷宫问题、图的连通性等。它沿着树的深度分支进行探索,直至达到叶子节点,若无法继续则回溯。例如,将数字6拆分为3个正整数的递增序列问题可以通过DFS实现,类似地,分糖果问题和买瓜问题同样可以用DFS求解。DFS通常涉及递归或栈结构,通过标记已访问节点避免重复。在编程中,会定义递归函数,设定结束条件,然后枚举可能的情况,并处理下一层节点。
|
26天前
|
人工智能 算法 Java
深度优先搜索(Depth-First Search,DFS)是一种用于遍历或搜索树或图的算法。
深度优先搜索(Depth-First Search,DFS)是一种用于遍历或搜索树或图的算法。
|
2天前
|
算法 数据挖掘
MATLAB数据分析、从算法到实现
MATLAB数据分析、从算法到实现
|
9天前
|
机器学习/深度学习 算法 调度
Matlab|基于改进鲸鱼优化算法的微网系统能量优化管理matlab-源码
基于改进鲸鱼优化算法的微网系统能量管理源码实现,结合LSTM预测可再生能源和负荷,优化微网运行成本与固定成本。方法应用于冷热电联供微网,结果显示经济成本平均降低4.03%,提高经济效益。代码包括数据分段、LSTM网络定义及训练,最终展示了一系列运行结果图表。