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

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

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

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

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

作者专栏每日更新:

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

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

python源码解读

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

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

题目描述

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

示例

示例 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

总结

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


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

相关文章
|
存储 人工智能 算法
从零掌握贪心算法Java版:LeetCode 10题实战解析(上)
在算法世界里,有一种思想如同生活中的"见好就收"——每次做出当前看来最优的选择,寄希望于通过局部最优达成全局最优。这种思想就是贪心算法,它以其简洁高效的特点,成为解决最优问题的利器。今天我们就来系统学习贪心算法的核心思想,并通过10道LeetCode经典题目实战演练,带你掌握这种"步步为营"的解题思维。
|
存储 算法 Java
算法系列之递归反转单链表
递归反转链表的基本思路是将当前节点的next指针指向前一个节点,然后递归地对下一个节点进行同样的操作。递归的核心思想是将问题分解为更小的子问题,直到达到基本情况(通常是链表末尾)。
622 5
算法系列之递归反转单链表
【算法】栈
栈相关算法题,供参考,附有链接地址及板书
326 14
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
565 4
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
454 2
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
449 2
|
机器学习/深度学习 算法 机器人
【水下图像增强融合算法】基于融合的水下图像与视频增强研究(Matlab代码实现)
【水下图像增强融合算法】基于融合的水下图像与视频增强研究(Matlab代码实现)
1076 0
|
数据采集 分布式计算 并行计算
mRMR算法实现特征选择-MATLAB
mRMR算法实现特征选择-MATLAB
631 2
|
传感器 机器学习/深度学习 编解码
MATLAB|主动噪声和振动控制算法——对较大的次级路径变化具有鲁棒性
MATLAB|主动噪声和振动控制算法——对较大的次级路径变化具有鲁棒性
551 3

热门文章

最新文章