LeetCode 题目 94:五种算法递归|迭代|莫里斯|线索二叉树|栈的迭代二叉树 实现中序遍历

简介: LeetCode 题目 94:五种算法递归|迭代|莫里斯|线索二叉树|栈的迭代二叉树 实现中序遍历

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

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

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

作者专栏每日更新:

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

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

python源码解读

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

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

本文详细探讨了五种二叉树中序遍历算法,包括递归、迭代、莫里斯遍历、线索二叉树和栈的迭代,评估了它们的效率和实用性。


题目描述

给定一个二叉树的根节点 root,返回它的中序遍历。

输入格式
  • root:二叉树的根节点。
输出格式
  • 返回中序遍历结果的列表。

示例

示例 1
输入: root = [1,null,2,3]
输出: [1,3,2]

方法一:递归

解题步骤
  1. 递归遍历:先遍历左子树,然后访问根节点,最后遍历右子树。
完整的规范代码
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def inorderTraversal(root):
    """
    递归实现二叉树的中序遍历
    :param root: TreeNode, 二叉树的根节点
    :return: List[int], 中序遍历的结果
    """
    def helper(node, res):
        if node:
            helper(node.left, res)
            res.append(node.val)
            helper(node.right, res)
    
    result = []
    helper(root, result)
    return result
# 示例调用
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)
print(inorderTraversal(root))  # 输出: [1,3,2]
算法分析
  • 时间复杂度:(O(n)),每个节点访问一次。
  • 空间复杂度:(O(h)),递归栈的深度,其中 (h) 是树的高度。

方法二:迭代

解题步骤
  1. 使用栈:利用栈来模拟递归过程,先深入访问左子树,再访问节点,最后处理右子树。
完整的规范代码
def inorderTraversal(root):
    """
    迭代实现二叉树的中序遍历
    :param root: TreeNode, 二叉树的根节点
    :return: List[int], 中序遍历的结果
    """
    stack, res = [], []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        res.append(current.val)
        current = current.right
    return res
# 示例调用
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)
print(inorderTraversal(root))  # 输出: [1,3,2]
算法分析
  • 时间复杂度:(O(n)),每个节点访问一次。
  • 空间复杂度:(O(h)),栈的最大深度等于树的高度。

方法三:莫里斯遍历 (Morris Traversal)

解题步骤
  1. 线索二叉树:利用叶子节点中的空 right 指针指向中序遍历的后继节点,从而实现空间复杂度为 (O(1)) 的遍历。
完整的规范代码
def inorderTraversal(root):
    """
    莫里斯遍历实现二叉树的中序遍历
    :param root: TreeNode, 二叉树的根节点
    :return: List[int], 中序遍历的结果
    """
    res, current = [], root
    while current:
        if current.left:
            # 找到左子树的最右节点
            pre = current.left
            while pre.right and pre.right != current:
                pre = pre.right
            if not pre.right:
                pre.right = current
                current = current.left
            else:
                pre.right = None
                res.append(current.val)
                current = current.right
        else:
            res.append(current.val)
            current = current.right
    return res
# 示例调用
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)
print(inorderTraversal(root))  # 输出: [1,3,2]
算法分析
  • 时间复杂度:(O(n)),尽管看似复杂,但每个节点最多被处理两次(一次连接前驱,一次断开前驱)。
  • 空间复杂度:(O(1)),不使用额外空间。

方法四:线索二叉树

解题步骤

线索二叉树是一种通过链接空的左指针指向节点的前驱,空的右指针指向节点的后继来增加遍历效率的方法。对于中序遍历,可以通过构建线索二叉树来无需额外空间和递归地完成遍历。

  1. 构建线索:在构建或遍历时,把空的左指针指向中序遍历的前驱,右指针指向后继。
  2. 遍历节点:从根节点开始,一直向左下走到最左,然后使用线索向右移动。
完整的规范代码
def inorderTraversal(root):
    """
    使用线索二叉树的方法进行中序遍历
    :param root: TreeNode, 二叉树的根节点
    :return: List[int], 中序遍历的结果
    """
    result = []
    current = root
    while current:
        if current.left:
            pre = current.left
            while pre.right and pre.right != current:
                pre = pre.right
            if not pre.right:
                pre.right = current  # 建立线索
                current = current.left
                continue
            pre.right = None  # 断开线索
        result.append(current.val)
        current = current.right
    return result
# 示例调用
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)
print(inorderTraversal(root))  # 输出: [1,3,2]
算法分析
  • 时间复杂度:(O(n)),每个节点被访问至多两次。
  • 空间复杂度:(O(1)),不使用额外空间,除了输出列表。

方法五:使用栈的非递归迭代

解题步骤

这种方法使用显式栈存储将要访问的节点,模拟递归过程。

  1. 使用栈:利用显式栈存储节点来模拟递归的调用栈。
  2. 处理节点:按照中序的顺序处理每个节点,即左-根-右。
完整的规范代码
def inorderTraversal(root):
    """
    使用栈的迭代方法进行中序遍历
    :param root: TreeNode, 二叉树的根节点
    :return: List[int], 中序遍历的结果
    """
    stack = []
    result = []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result
# 示例调用
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)
print(inorderTraversal(root))  # 输出: [1,3,2]
算法分析
  • 时间复杂度:(O(n)),每个节点被访问一次。
  • 空间复杂度:(O(h)),栈的最大深度等于树的高度。

下面是五种中序遍历二叉树算法的优劣势对比表,这有助于直观地了解每种方法的特点和适用场景:

方法 时间复杂度 空间复杂度 优势 劣势
递归 (O(n)) (O(h)) 简单直观;直接符合中序遍历定义。 可能导致栈溢出;递归深度受树高限制。
迭代 (O(n)) (O(h)) 避免递归导致的栈溢出。 实现较为复杂;需要手动维护栈。
莫里斯遍历 (O(n)) (O(1)) 不使用额外空间;适合内存限制严格的环境。 修改树的结构(临时);实现复杂,难以掌握。
线索二叉树 (O(n)) (O(1)) 通过线索化减少空间使用,无栈无递归。 需要修改树的结构,实现较复杂。
栈的迭代 (O(n)) (O(h)) 易于理解和实现;不修改树的结构。 需要额外的存储空间模拟调用栈。

应用示例

  • 算法设计与数据结构教育:递归和迭代方法经常用于教学,展示基本的树遍历技术。
  • 计算机图形学:中序遍历可用于场景图管理,处理具有层次结构的图形对象。
  • 编译器构建:在抽象语法树(AST)的处理中,中序遍历可以用于生成输出代码或。

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

相关文章
|
15天前
|
存储 算法 测试技术
力扣经典150题第五十四题:最小栈
力扣经典150题第五十四题:最小栈
15 0
|
18天前
|
存储 算法 索引
力扣每日一题 6/24 模拟 数组 单调栈
力扣每日一题 6/24 模拟 数组 单调栈
8 0
|
21天前
|
存储 算法
【数据结构和算法】--- 二叉树(4)--二叉树链式结构的实现(2)
【数据结构和算法】--- 二叉树(4)--二叉树链式结构的实现(2)
15 0
|
11天前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
11 3
|
21天前
|
算法 分布式数据库
【数据结构和算法】--- 二叉树(5)--二叉树OJ题
【数据结构和算法】--- 二叉树(5)--二叉树OJ题
12 1
|
6天前
|
Python
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
|
11天前
|
算法 JavaScript
JS 【详解】二叉树(含二叉树的前、中、后序遍历技巧和算法实现)
JS 【详解】二叉树(含二叉树的前、中、后序遍历技巧和算法实现)
18 0
|
21天前
|
算法
【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)
【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)
6 0
|
21天前
|
存储 算法
【数据结构和算法】---二叉树(2)--堆的实现和应用
【数据结构和算法】---二叉树(2)--堆的实现和应用
10 0
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题