参照的是左程云的课程：https://space.bilibili.com/8888480/lists/3509640?type=series
本笔记包括了二叉树的基础概念、三种遍历方式的递归实现和非递归实现，涵盖了先序、中序、后序遍历的原理与代码实现，包括了class017 -> class018的内容

017【入门】二叉树及其三种序的递归实现

二叉树的基本概念

二叉树是一种重要的树形数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树是许多高级数据结构和算法的基础。

二叉树节点定义

class TreeNode:
    def __init__(self, v):
        self.val = v         # 节点的值
        self.left = None     # 左子节点
        self.right = None    # 右子节点

递归序的概念

递归序是理解二叉树遍历的关键概念。对于任意二叉树节点，递归过程会经过该节点三次：

def f(head):
    if head is None:
        return
    # 第1次到达该节点 - 刚进入该节点
    f(head.left)   # 递归处理左子树
    # 第2次到达该节点 - 左子树处理完毕
    f(head.right)  # 递归处理右子树
    # 第3次到达该节点 - 右子树处理完毕

根据在这三个时机中选择处理节点的时机不同，就形成了三种不同的遍历方式。

二叉树的三种递归遍历

先序遍历（Pre-order Traversal）

先序遍历的顺序是：根节点 → 左子树 → 右子树

@staticmethod
def preOrder(head):
    """
    先序遍历：在第1次到达节点时处理
    应用场景：复制二叉树、表达式树求值、目录树打印
    测试链接LeetCode 144. 二叉树的前序遍历https://leetcode.cn/problems/binary-tree-preorder-traversal/
    """
    if head is None:
        return
    print(head.val, end=" ")  # 先处理当前节点
    BinaryTreeTraversalRecursion.preOrder(head.left)   # 再遍历左子树
    BinaryTreeTraversalRecursion.preOrder(head.right)  # 最后遍历右子树

中序遍历（In-order Traversal）

中序遍历的顺序是：左子树 → 根节点 → 右子树

@staticmethod
def inOrder(head):
    """
    中序遍历：在第2次到达节点时处理
    应用场景：二叉搜索树排序（得到有序序列）、表达式树转中缀表达式
    测试链接LeetCode 94. 二叉树的中序遍历：https://leetcode.cn/problems/binary-tree-inorder-traversal/
    """
    if head is None:
        return
    BinaryTreeTraversalRecursion.inOrder(head.left)   # 先遍历左子树
    print(head.val, end=" ")  # 再处理当前节点
    BinaryTreeTraversalRecursion.inOrder(head.right)  # 最后遍历右子树

后序遍历（Post-order Traversal）

后序遍历的顺序是：左子树 → 右子树 → 根节点

@staticmethod
def posOrder(head):
    """
    后序遍历：在第3次到达节点时处理
    应用场景：计算目录大小、删除二叉树、表达式树计算
    测试链接LeetCode 145. 二叉树的后序遍历：https://leetcode.cn/problems/binary-tree-postorder-traversal/
    """
    if head is None:
        return
    BinaryTreeTraversalRecursion.posOrder(head.left)   # 先遍历左子树
    BinaryTreeTraversalRecursion.posOrder(head.right)  # 再遍历右子树
    print(head.val, end=" ")  # 最后处理当前节点

递归遍历的示例执行

以下面的二叉树为例：

执行结果对比

先序遍历结果：1 2 4 5 3 6 7
中序遍历结果：4 2 5 1 6 3 7
后序遍历结果：4 5 2 6 7 3 1

递归调用过程分析

以先序遍历为例，递归调用的过程：

访问节点1，打印1
递归进入左子树（节点2）
- 访问节点2，打印2
- 递归进入左子树（节点4）
  - 访问节点4，打印4
  - 左右子树为空，返回
- 递归进入右子树（节点5）
  - 访问节点5，打印5
  - 左右子树为空，返回
递归进入右子树（节点3）
- 类似过程…

复杂度分析

时间复杂度

所有递归遍历算法的时间复杂度都是 O(n)，其中n是二叉树的节点数。每个节点都会被访问恰好一次。

空间复杂度

额外空间复杂度：O(h)，其中h是树的高度。

最好情况（完全平衡的二叉树）：h = ⌊log₂n⌋，空间复杂度为O(log n)
最坏情况（完全不平衡的树，退化为链表）：h = n，空间复杂度为O(n)
平均情况：对于随机二叉树，h = O(log n)

空间消耗主要来自递归调用栈，栈的最大深度等于树的高度。

三种遍历方式的应用场景

先序遍历的典型应用

复制二叉树：先创建根节点，再递归复制左右子树
表达式树求值：先处理操作符，再处理操作数
目录树打印：先打印目录名，再打印子目录内容
序列化二叉树：将树结构转换为字符串格式

# 复制二叉树示例
def copyTree(root):
    if root is None:
        return None
    # 先创建新节点（先序特点）
    newNode = TreeNode(root.val)
    newNode.left = copyTree(root.left)    # 递归复制左子树
    newNode.right = copyTree(root.right)  # 递归复制右子树
    return newNode

中序遍历的典型应用

二叉搜索树排序：中序遍历BST得到有序序列
表达式树转中缀表达式：按照运算符优先级添加括号
验证二叉搜索树：检查中序遍历结果是否为递增序列

# 验证二叉搜索树示例
def isValidBST(root):
    def inorder(node, values):
        if node is None:
            return
        inorder(node.left, values)
        values.append(node.val)  # 中序收集值
        inorder(node.right, values)
    
    values = []
    inorder(root, values)
    # 检查是否严格递增
    return all(values[i] < values[i+1] for i in range(len(values)-1))

后序遍历的典型应用

计算目录大小：先计算子目录大小，再计算当前目录
删除二叉树：先删除子节点，再删除父节点
表达式树计算：先计算子表达式，再计算根表达式
计算树的高度：先计算子树高度，再计算当前树高度

# 计算二叉树高度示例
def maxDepth(root):
    if root is None:
        return 0
    # 先计算左右子树高度（后序特点）
    leftHeight = maxDepth(root.left)
    rightHeight = maxDepth(root.right)
    # 再计算当前树高度
    return max(leftHeight, rightHeight) + 1

遍历方式选择指南

需求场景	推荐遍历方式	理由
复制/构建树结构	先序遍历	需要先创建根节点
获取有序数据	中序遍历	BST的中序遍历有序
释放/计算资源	后序遍历	需要先处理子节点
树的序列化	先序遍历	便于重建树结构
表达式求值	后序遍历	需要先计算子表达式

递归实现的优缺点

优点

代码简洁：逻辑清晰，易于理解和实现
自然表达：完美匹配树的递归定义
易于扩展：容易添加额外的处理逻辑

缺点

栈溢出风险：深度递归可能导致栈溢出
性能开销：函数调用的开销相对较大
难以控制：无法方便地暂停或恢复遍历过程

在实际应用中，对于一般规模的二叉树，递归实现是首选方案。当树的深度可能很大时，需要考虑使用非递归实现来避免栈溢出问题。

018【入门】二叉树遍历的非递归实现和复杂度分析

非递归实现的必要性

递归实现虽然简洁易懂，但在处理大型树时可能导致栈溢出。非递归实现使用显式栈来模拟递归过程，提供了更好的控制性和避免栈溢出的优势。

核心思想

用显式的栈数据结构来模拟系统递归调用栈的行为，手动管理遍历过程中的状态信息。

先序遍历的非递归实现

实现原理

先序遍历要求”根-左-右”的访问顺序。使用栈时，由于栈是LIFO（后进先出）结构，需要先压入右子节点，再压入左子节点，这样弹栈时就是先处理左子树。

@staticmethod
def preOrder(head):
    """
    先序遍历非递归实现
    核心思路：使用一个栈。每次先访问节点本身，再依次压入右、左子节点（注意顺序，先右后左），这样弹栈时总是优先处理左子树，实现“中-左-右”顺序
    时间复杂度：O(n)，每个节点进栈出栈各一次
    空间复杂度：O(h)，h为树的高度
    测试链接LeetCode 144. 二叉树的前序遍历https://leetcode.cn/problems/binary-tree-preorder-traversal/
    """
    if head is not None:
        stack = []
        stack.append(head)
        while stack:
            head = stack.pop()        # 弹出栈顶节点
            print(head.val, end=" ")  # 立即打印（先序特点）
            # 关键：先压右子节点，再压左子节点
            # 这样弹栈时就是先处理左子树，再处理右子树
            if head.right is not None:
                stack.append(head.right)
            if head.left is not None:
                stack.append(head.left)
        print()

执行过程示例

以树 1(2(4,5),3(6,7)) 为例：

步骤	栈状态	弹出节点	打印	压入节点
初始	[1]	-	-	-
1	[3,2]	1	1	3,2
2	[3,5,4]	2	2	5,4
3	[3,5]	4	4	-
4	[3]	5	5	-
5	[7,6]	3	3	7,6
6	[7]	6	6	-
7	[]	7	7	-

输出结果：1 2 4 5 3 6 7

中序遍历的非递归实现

实现原理

中序遍历要求”左-根-右”的访问顺序。需要先沿着左子树走到底，将路径上的所有节点压栈，然后开始弹栈处理节点，并转向右子树。

@staticmethod
def inOrder(head):
    """
    中序遍历非递归实现
    核心思路：用一个栈模拟递归。每次不断沿左子树走到底，并将沿途所有节点入栈；遇到空节点就弹出栈顶节点，访问它，然后转向其右子树。如此反复，完整地实现“左-中-右”顺序。
    测试链接LeetCode 94. 二叉树的中序遍历：https://leetcode.cn/problems/binary-tree-inorder-traversal/
    """
    if head is not None:
        stack = []
        while stack or head is not None:
            if head is not None:
                # 当前节点不为空，压栈并继续向左
                stack.append(head)
                head = head.left
            else:
                # 当前节点为空，说明左子树遍历完毕
                head = stack.pop()        # 弹出栈顶节点
                print(head.val, end=" ")  # 打印节点值（中序特点）
                head = head.right         # 转向右子树
        print()

算法状态分析

中序遍历的非递归实现有两种状态：

下降状态：head != None，沿左子树向下走并压栈
上升状态：head == None，弹栈处理节点并转向右子树

执行过程示例

以树 1(2(4,5),3(6,7)) 为例：

步骤	head	栈状态	操作	打印
初始	1	[]	-	-
1	2	[1]	压栈1，左移	-
2	4	[1,2]	压栈2，左移	-
3	None	[1,2,4]	压栈4，左移	-
4	4	[1,2]	弹栈4	4
5	None	[1,2]	4右移(None)	-
6	2	[1]	弹栈2	2
7	5	[1]	2右移到5	-
8	None	[1,5]	压栈5，左移	-
…	…	…	…	…

输出结果：4 2 5 1 6 3 7

后序遍历的非递归实现

后序遍历是最复杂的，因为需要确保在访问根节点之前，左右子树都已经被完全访问。提供两种实现方法：

方法一：使用两个栈

@staticmethod
def posOrderTwoStacks(head):
    """
    后序遍历非递归实现 - 双栈法
    核心思路：第一个栈实现"中-右-左"遍历，结果压入第二个栈
    最后弹出第二个栈得到"左-右-中"的后序遍历结果
    即：用一个栈模拟递归。每次不断沿左子树走到底，并将沿途所有节点入栈；遇到空节点就弹出栈顶节点，访问它，然后转向其右子树。如此反复，完整地实现“左-中-右”顺序。
    测试链接LeetCode 145. 二叉树的后序遍历：https://leetcode.cn/problems/binary-tree-postorder-traversal/
    """
    if head is not None:
        stack = []      # 主栈：用于遍历
        collect = []    # 收集栈：用于收集结果
        stack.append(head)
        
        while stack:
            head = stack.pop()
            collect.append(head)      # 收集节点到第二个栈
            # 注意：这里先压左子节点，再压右子节点
            # 这样遍历顺序就是"中-右-左"
            if head.left is not None:
                stack.append(head.left)
            if head.right is not None:
                stack.append(head.right)
        
        # 反向弹出收集栈，得到"左-右-中"顺序
        while collect:
            print(collect.pop().val, end=" ")
        print()

双栈法原理解析

第一阶段：用第一个栈实现”中-右-左”遍历，类似先序遍历但左右子节点入栈顺序相反
第二阶段：将第一阶段的结果压入第二个栈
第三阶段：弹出第二个栈，得到”左-右-中”的后序遍历结果

关键洞察：”中-右-左”的逆序正好是”左-右-中”

方法二：使用一个栈

@staticmethod
def posOrderOneStack(h):
    """
    后序遍历非递归实现 - 单栈法
    核心思路：通过记录最近访问的节点，确保每个节点在其左右子树都被访问后才访问自己，从而严格实现“左-右-中”的后序遍历。
    每个节点最多入栈两次，效率更高
    测试链接LeetCode 145. 二叉树的后序遍历：https://leetcode.cn/problems/binary-tree-postorder-traversal/
    """
    if h is not None:
        stack = []
        stack.append(h)
        # h的含义：最近一次处理（打印）的节点
        
        while stack:
            cur = stack[-1]  # 查看栈顶元素但不弹出
            
            # 情况1：有左子树且左子树未被处理过
            if cur.left is not None and h != cur.left and h != cur.right:
                stack.append(cur.left)
            # 情况2：有右子树且右子树未被处理过
            elif cur.right is not None and h != cur.right:
                stack.append(cur.right)
            # 情况3：左右子树都没有或都已处理完毕
            else:
                print(cur.val, end=" ")
                h = stack.pop()  # 更新h为刚刚处理的节点
        print()

单栈法状态管理

核心变量h的含义变化：

初始时：h指向根节点（但实际表示”还没有处理过任何节点”）
处理过程中：h始终指向最近一次处理（打印）的节点
判断逻辑：通过比较当前节点的子节点与h的关系，判断子树是否已被处理

三种处理情况：

有左子树且未处理：cur.left != None and h != cur.left and h != cur.right
有右子树且未处理：cur.right != None and h != cur.right
可以处理当前节点：左右子树都不存在或都已处理完毕

复杂度分析对比

时间复杂度

所有非递归遍历算法的时间复杂度都是 O(n)：

先序和中序：每个节点进栈出栈各一次
后序双栈法：每个节点进栈出栈总共两次（每个栈一次）
后序单栈法：每个节点最多进栈两次，出栈一次

空间复杂度

额外空间复杂度对比：

实现方法	空间复杂度	说明
先序非递归	O(h)	一个栈，最大深度为树高
中序非递归	O(h)	一个栈，最大深度为树高
后序双栈法	O(n)	收集栈最坏情况存储所有节点
后序单栈法	O(h)	一个栈，最大深度为树高
递归实现	O(h)	系统调用栈，深度为树高

其中h为树的高度：

最好情况：h = O(log n)（平衡树）
最坏情况：h = O(n)（退化为链表）

实现方法选择建议

性能对比

方法	时间复杂度	空间复杂度	实现难度	推荐场景
先序非递归	O(n)	O(h)	简单	通用推荐
中序非递归	O(n)	O(h)	中等	BST相关问题
后序双栈法	O(n)	O(n)	简单	理解后序遍历逻辑
后序单栈法	O(n)	O(h)	困难	空间要求严格的场景

选择建议

实际应用：根据具体需求选择，一般情况下递归实现更简洁
性能要求高：选择非递归实现，避免函数调用开销
内存受限：后序遍历优选单栈法，其他遍历方式空间复杂度相当

非递归实现的优势

避免栈溢出：可以处理任意深度的树
更好控制：可以方便地暂停、恢复遍历过程
性能优化：减少函数调用开销
状态保存：便于在遍历过程中保存额外信息

非递归实现虽然代码复杂度较高，但在处理大规模数据或有特殊要求的场景中具有重要意义。