基础数据结构-111-二叉树-e05-最大深度-解法3

二叉树最大深度计算之层序遍历法详解

方法思想
层序遍历法通过统计二叉树的层数来确定最大深度。核心原理是：二叉树的层数即为树的最大深度。使用队列数据结构实现层序遍历，通过分层处理节点来统计层数。

实现步骤

1. 基础层序遍历框架

public int maxDepth(TreeNode root) {
    if (root == null) return 0;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int depth = 0;

    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        depth++;

        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    return depth;
}

2. 关键实现要点

3. 队列选择：使用JDK的LinkedList实现队列接口

4. 分层处理：
   • 通过queue.size()获取当前层节点数

   • 使用嵌套循环处理每一层节点

5. 深度统计：每处理完一层，深度计数器+1

6. 执行过程示例
   以二叉树：

    1
   / \
  2   3
 / \   \
4   5   6
   /
  7

遍历过程：

1. 第1层：1 → depth=1
2. 第2层：2,3 → depth=2
3. 第3层：4,5,6 → depth=3
4. 第4层：7 → depth=4

特殊处理
• 空树处理：当root为null时直接返回深度0

• 子节点判空：添加子节点前需判断非空，避免加入null节点

方法对比

方法类型	时间复杂度	空间复杂度	实现难度
递归后序遍历	O(n)	O(h)	易
非递归后序遍历	O(n)	O(n)	较难
层序遍历	O(n)	O(n)	中等

注意事项

1. 使用LinkedList作为队列时注意：
   • 入队使用offer()

   • 出队使用poll()

2. 分层处理的两种实现方式：
   • 通过临时变量记录每层节点数（通用性强）

   • 直接使用queue.size()获取（需队列实现支持）

3. 测试案例要覆盖：
   • 空树

   • 单节点树

   • 完全不平衡树

   • 满二叉树

效率分析
• 最优方案：递归后序遍历（空间复杂度最优）

• 层序遍历优势：容易理解，可直观观察遍历过程

• 适用场景：需要按层处理节点时（如打印树结构、求每层平均值等）

该方法将树的结构特性转化为层数统计问题，通过队列的分层处理机制，实现了时间复杂度为O(n)的解决方案。相比递归方法虽然空间复杂度稍高，但避免了递归栈溢出的风险，适合处理深度较大的树结构。

基础数据结构-112-二叉树-e06-最小深度

求二叉树的最小深度课程文档

问题描述
给定一棵二叉树，求其最小深度。最小深度定义为从根节点到最近叶子节点的最短路径上的节点数量。

错误解法分析
错误递归思路

1. 初始递归代码：

def minDepth(node):
    if node is None:
        return 0
    left_depth = minDepth(node.left)
    right_depth = minDepth(node.right)
    return min(left_depth, right_depth) + 1

2. 错误案例验证：

测试用例：
    1
   /
  2
期望结果：2
实际输出：1

3. 错误原因：
   当某子树为空时（如右子树为None），错误地将其深度视为0参与计算。实际上这种情况下应忽略空子树，只考虑有效子树深度。

正确解法（递归法）
修正后的递归逻辑

def minDepth(root):
    if not root:
        return 0

    left = minDepth(root.left)
    right = minDepth(root.right)

    # 处理单边为空的情况
    if left == 0:
        return right + 1
    if right == 0:
        return left + 1

    # 正常情况取最小值
    return min(left, right) + 1

关键修正点

1. 当左子树为空时，直接返回右子树深度+1
2. 当右子树为空时，直接返回左子树深度+1
3. 仅当左右子树均非空时才取最小值

高效解法（层序遍历法）
算法思路
使用广度优先搜索（BFS）进行层序遍历，第一个遇到的叶子节点所在层即为最小深度。

实现代码

from collections import deque

def minDepth(root):
    if not root:
        return 0

    queue = deque([root])
    depth = 0

    while queue:
        depth += 1
        level_size = len(queue)

        for _ in range(level_size):
            node = queue.popleft()

            # 找到第一个叶子节点
            if not node.left and not node.right:
                return depth

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return depth

算法优势

1. 时间复杂度：O(n)，最坏情况需遍历所有节点
2. 空间复杂度：O(n)
3. 实际运行效率优于递归法，遇到第一个叶子节点即可提前返回

测试用例

用例图示	树结构描述	预期结果	两种方法验证
①	空树	0	通过
②	单节点树	1	通过
③	完全平衡树	2	通过
④	左单链结构	2	递归法需修正

关键总结

1. 与最大深度的本质区别：
   • 最大深度：必须走到最深层

   • 最小深度：找到最近叶子节点即可

2. 递归法注意事项：
   • 需特殊处理单边子树为空的情况

   • 基线条件（root为None时返回0）保持不变

3. 层序遍历优势：
   • 避免无效的深度计算

   • 更符合"最小深度"的物理意义

   • 适合处理极端不平衡树的情况

扩展思考
当二叉树节点数量为n时，两种方法的时间复杂度均为O(n)，但实际运行中BFS方法在多数情况下能更快返回结果，特别是在最小深度较小时优势明显。建议在实际工程应用中优先选择层序遍历实现。

基础数据结构-113-二叉树-e07-翻转二叉树

翻转二叉树详解

题目描述
给定一棵二叉树的根节点 root，要求通过交换每个节点的左右子树，实现二叉树的镜像翻转。最终返回翻转后的二叉树根节点。

示例分析
原始二叉树结构

       1
     /   \
    2     3
   / \
  4   5
     / \
    7   8

翻转过程分解

1. 根节点处理：交换节点1的左右子树（节点2和节点3）

2. 子树递归处理：
   • 处理节点2：交换其左右子节点4和5

   • 处理节点5：交换其左右子节点7和8

3. 终止条件：当遇到空节点时停止递归

翻转后结构

       1
     /   \
    3     2
         / \
        5   4
       / \
      8   7

解题思路
采用递归法实现二叉树翻转，核心逻辑分为三步：

1. 交换当前节点左右子树
2. 递归处理左子树
3. 递归处理右子树

算法实现

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        def dfs(node):
            # 递归终止条件：空节点直接返回
            if not node:
                return

            # 交换当前节点的左右子树
            node.left, node.right = node.right, node.left

            # 递归处理左右子树
            dfs(node.left)
            dfs(node.right)

        # 从根节点开始处理
        dfs(root)
        return root

复杂度分析
• 时间复杂度：O(n)

每个节点仅被访问一次，n为树节点总数
• 空间复杂度：O(h)

h为树的高度，递归栈空间取决于树的高度（最坏情况为O(n)）

关键点解析

1. 递归终止条件：当节点为 None 时停止递归
2. 交换顺序：先交换当前节点左右子树，再递归处理子节点
3. 返回值处理：始终返回原始根节点，因其位置不变仅子节点被交换

常见问题
Q：如何处理空树的情况？
A：当 root 为 None 时，函数直接返回 None，符合边界条件处理。

Q：为什么不需要新建二叉树？
A：直接在原二叉树节点上交换左右指针，实现了空间复杂度 O(1) 的原地修改。

基础数据结构-114-二叉树-e08-根据后缀表达式建树

根据后缀表达式构造表达式树（二叉树）详解

一、问题背景
给定一个合法的后缀表达式（逆波兰表达式），要求构造对应的表达式二叉树。假设所有运算符均为二元运算符，且表达式只包含数字和加减乘除运算符。

基本概念
• 中缀表达式：人类常用的表达式形式（如 (2-1)*3）

• 后缀表达式：运算符位于操作数之后的表达式（如 2 1 - 3 *）

• 表达式树特性：

• 叶子节点为操作数

• 非叶子节点为运算符

• 父节点的左子树为左操作数，右子树为右操作数

二、算法思路
核心思想
利用栈结构处理后缀表达式，遵循以下规则：

1. 遇到操作数时创建节点并入栈

2. 遇到运算符时：
   • 弹出栈顶两个元素作为右、左操作数

   • 创建以运算符为值的父节点

   • 将新节点入栈

示例解析
以 ["2", "1", "-", "3", "*"] 为例：

1. 处理前三个元素 2, 1, -：
   • 创建节点 2 和 1 入栈

   • 遇到 - 时弹出 1（右孩子）、2（左孩子）

   • 创建父节点 -，其左右子树分别为 2 和 1，将 - 入栈

2. 处理后两个元素 3, *：
   • 创建节点 3 入栈

   • 遇到 * 时弹出 3（右孩子）、-（左孩子）

   • 创建父节点 *，其左右子树分别为 - 和 3

最终栈顶元素即为树的根节点，对应表达式树结构：

    *
   / \
  -   3
 / \
2   1

三、代码实现

class TreeNode {
    String val;
    TreeNode left;
    TreeNode right;
    TreeNode(String x) { val = x; }
}

public class Solution {
    public TreeNode buildTree(String[] tokens) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        for (String token : tokens) {
            if (isOperator(token)) {
                TreeNode right = stack.pop();
                TreeNode left = stack.pop();
                TreeNode parent = new TreeNode(token);
                parent.left = left;
                parent.right = right;
                stack.push(parent);
            } else {
                stack.push(new TreeNode(token));
            }
        }
        return stack.pop();
    }

    private boolean isOperator(String s) {
        return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");
    }
}

四、验证方法
通过后序遍历验证树结构正确性：

1. 对构造的表达式树执行后序遍历
2. 遍历结果应与原始后缀表达式一致

验证代码示例

List<String> result = new ArrayList<>();
postOrder(root, result);
assert Arrays.equals(result.toArray(), new String[]{"2", "1", "-", "3", "*"});

五、关键点总结

1. 栈操作顺序：先弹出右操作数，后弹出左操作数

2. 时间复杂度：O(n)，线性扫描表达式一次

3. 空间复杂度：O(n)，栈空间最大存储所有操作数

4. 扩展应用：
   • 中缀表达式转后缀表达式

   • 表达式树的前序、中序遍历应用

   • 表达式计算的递归实现

六、补充说明
• 后序遍历与表达式关系：对表达式树进行后序遍历可直接得到原始后缀表达式

• 错误处理：实际应用中需增加对非法表达式的检测（如操作数不足、无效字符等）

• 优化方向：支持多元运算符、函数调用等复杂表达式处理

基础数据结构-115-二叉树-e09-根据前中遍历结果建树

根据前序和中序遍历结果还原二叉树详解

---

问题描述
给定一个二叉树的前序遍历结果[1,2,4,3,6,7]和中序遍历结果[4,2,1,6,3,7]，要求还原原始的二叉树结构。

---

核心思路

1. 前序遍历特点
   第一个元素一定是根节点，后续元素按根-左子树-右子树顺序排列，但无法直接区分左右子树的分界点。

2. 中序遍历特点
   根节点左侧为左子树，右侧为右子树。例如，若根节点为1，则左子树为[4,2]，右子树为[6,3,7]。

3. 递归拆分
   通过前序确定根节点，利用中序划分左右子树的范围，递归处理左右子问题。

---

算法步骤

1. 确定根节点
   前序数组的首元素为根节点值（如示例中的1）。

2. 分割中序数组
   在中序数组中找到根节点位置i，左侧为左子树（长度len_left），右侧为右子树。

3. 分割前序数组
   根据左子树长度len_left，前序数组中[1:1+len_left]为左子树，剩余部分为右子树。

4. 递归构建子树
   对左右子树的前序和中序子数组重复上述步骤，直到数组为空。

---

示例分析

遍历类型	原始数组	根节点	左子树	右子树
前序遍历	[1,2,4,3,6,7]	1	[2,4]	[3,6,7]
中序遍历	[4,2,1,6,3,7]	1	[4,2]	[6,3,7]

• 左子树递归

前序[2,4]和中序[4,2]，根节点为2，左子节点为4。

• 右子树递归

前序[3,6,7]和中序[6,3,7]，根节点为3，左子节点为6，右子节点为7。

---

代码实现（Java）

import java.util.Arrays;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 终止条件：空数组返回null
        if (preorder.length == 0 || inorder.length == 0) {
            return null;
        }

        // 创建根节点
        int rootVal = preorder[0];
        TreeNode root = new TreeNode(rootVal);

        // 在中序数组中找到根节点位置
        int rootIndex = 0;
        for (; rootIndex < inorder.length; rootIndex++) {
            if (inorder[rootIndex] == rootVal) {
                break;
            }
        }

        // 分割中序数组（左/右子树）
        int[] inLeft = Arrays.copyOfRange(inorder, 0, rootIndex);
        int[] inRight = Arrays.copyOfRange(inorder, rootIndex + 1, inorder.length);

        // 分割前序数组（左/右子树）
        int[] preLeft = Arrays.copyOfRange(preorder, 1, 1 + rootIndex);
        int[] preRight = Arrays.copyOfRange(preorder, 1 + rootIndex, preorder.length);

        // 递归构建左右子树
        root.left = buildTree(preLeft, inLeft);
        root.right = buildTree(preRight, inRight);

        return root;
    }
}

---

复杂度分析
• 时间复杂度：O(n²)

每次递归需遍历中序数组寻找根节点（O(n)），共递归n次。
• 空间复杂度：O(n)

递归栈深度和数组拷贝的额外空间。

---

关键点总结

1. 前序定根，中序分界
   前序首元素为根节点，中序根节点位置确定左右子树范围。
2. 递归终止条件
   当子数组长度为0时停止递归。
3. 数组拷贝优化
   可通过传递索引代替实际数组拷贝，将复杂度优化至O(n)。

基础数据结构-116-二叉树-e10-根据中后遍历结果建树

根据中序与后序遍历还原二叉树的详细解题文档

题目描述
给定一个二叉树的中序遍历结果 inorder 和后序遍历结果 postorder，要求还原这棵二叉树。假设所有节点的值唯一。

解题思路
核心思想
利用二叉树遍历的特性进行递归构建：

1. 后序遍历的最后一个元素是当前子树的根节点
2. 中序遍历中根节点将序列分为左右子树两部分

与上题对比
• 上题（前序+中序）：前序首元素为根节点

• 本题（中序+后序）：后序末元素为根节点

算法步骤

1. 定位根节点
   • 后序遍历数组的最后一个元素即为当前子树的根节点值

2. 划分左右子树

3. 中序遍历划分：
   • 根据根节点值在中序数组中找到索引 index

   • 左子树：in_left = inorder[0..index-1]

   • 右子树：in_right = inorder[index+1..end]

4. 后序遍历划分：
   • 左子树长度与中序左子树相同

   • 左子树：post_left = postorder[0..left_size-1]

   • 右子树：post_right = postorder[left_size..end-1]（排除末位根节点）

5. 递归构建
   • 用划分后的左右子树数组递归构建左右子节点

代码实现

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // 递归终止条件
        if (inorder.length == 0 || postorder.length == 0) return null;

        // 确定根节点
        int rootVal = postorder[postorder.length - 1];
        TreeNode root = new TreeNode(rootVal);

        // 查找中序遍历中的根节点位置
        int index = 0;
        for (; index < inorder.length; index++) {
            if (inorder[index] == rootVal) break;
        }

        // 划分左右子树
        int[] in_left = Arrays.copyOfRange(inorder, 0, index);
        int[] in_right = Arrays.copyOfRange(inorder, index + 1, inorder.length);

        int[] post_left = Arrays.copyOfRange(postorder, 0, index);
        int[] post_right = Arrays.copyOfRange(postorder, index, postorder.length - 1);

        // 递归构建
        root.left = buildTree(in_left, post_left);
        root.right = buildTree(in_right, post_right);

        return root;
    }
}

复杂度分析
• 时间复杂度：O(n²)

• 每次递归需要遍历查找根节点位置

• 数组拷贝操作增加时间消耗

• 空间复杂度：O(n)

• 递归调用栈深度

• 每次递归创建新数组

优化建议

1. 哈希表优化查找
   • 预处理中序数组，建立值->索引的哈希映射

• 将查找根节点时间复杂度从 O(n) 降为 O(1)

2. 索引传递代替数组拷贝
   • 通过传递数组索引范围代替创建新数组

• 例如：使用 (inStart, inEnd) 和 (postStart, postEnd) 标记当前处理范围

优化后效果
• 时间复杂度可优化至 O(n)

• 空间复杂度优化至 O(n)（主要来自递归栈）

示例演示
假设输入：

中序 inorder = [4, 2, 1, 6, 3, 7]
后序 postorder = [4, 2, 6, 7, 3, 1]

构建过程：

1. 根节点为1，划分中序：
   • 左子树：[4,2]

   • 右子树：[6,3,7]

2. 对应后序划分：
   • 左子树后序：[4,2]

   • 右子树后序：[6,7,3]

3. 递归构建左右子树，最终得到完整二叉树结构。

关键点总结

1. 后序末位始终是当前根节点
2. 中序划分确定左右子树元素集合
3. 保持左右子树元素数量一致性
4. 递归处理时注意数组边界条件

通过这种分治递归的方法，可以高效还原二叉树结构，后续优化能显著提升算法性能。