一、什么是二叉树？（基础概念解析）

1. 定义与结构特点

二叉树是一种树形数据结构，每个节点最多拥有两个子节点，分别称为左子树和右子树。其核心特点：

• 根节点：无父节点的顶层节点；

• 叶子节点：无左右子树的节点；

• 节点的度：该节点拥有的子树数量（二叉树中节点度最大为 2）；

• 树的深度：从根节点到最远叶子节点的最长路径长度。

图片示例

二、二叉树的存储方式

1. 顺序存储（数组）

原理：按层序遍历顺序，将节点值存入数组，通过索引计算父子节点位置：

• 父节点索引 i → 左子节点索引 2i+1，右子节点索引 2i+2；

• 子节点索引 j → 父节点索引 (j-1)//2。

优点：访问速度快，无需额外存储指针；缺点：适合完全二叉树，非完全二叉树会浪费大量数组空间。

2. 链式存储（链表）

原理：每个节点包含「数据域」和「两个指针域」（左指针 left、右指针 right），通过指针连接子节点。

节点结构（Java 示例）：

• 优点：空间利用率高，适合任意形态二叉树；

• 缺点：访问节点需通过指针遍历。

三、二叉树核心算法：遍历（必掌握）

二叉树遍历是所有操作的基础，核心分为「深度优先遍历（DFS）」和「广度优先遍历（BFS）」，本文详解深度遍历。

1. 深度优先遍历的三种顺序

优先遍历子树，分为三种顺序（以根节点 R、左子树 L、右子树 R 为核心）：

（1）前序遍历（根 → 左 → 右）

图片示例：

输出内容: A、B、D、E、C、F、G

JAVA 代码展示：

（2）中序遍历（左 → 根 → 右）

图片示例：

输出内容: D、B、E、A、C、F、G

JAVA 代码展示：

（3）后序遍历（左 → 右 → 根）

图片示例：

输出内容: D、E、B、F、G、C、A

JAVA 代码展示：

三种遍历的核心共性

1. 递归边界一致：均以 root == null 作为终止条件，避免空指针异常；

2. 都是从树的顶端开始遍历，只不过是输出的顺序不同；

3. 时间复杂度：均为 O(n)（每个节点遍历一次），空间复杂度：均为 O(h)（h 为树的深度，递归栈占用空间）。

四、二叉树高频面试题实战

1. 题目 1：计算二叉树的最大深度

问题描述：求从根节点到最远叶子节点的最长路径长度（对应 LeetCode 104 号题）；

思路：首先看到题目，我们想到的一件事就是从上到下给他遍历一次，当遇到递归节点时，给他加 1，最后输出结果，就大功告成了。

这又出现了几个问题：

• 用那种遍历方式呢？

• 如果只在左子树或右子树递归加 1 就输出内容，但是不是其中最大的深度怎么办？

• 是在左子树递归时加 1 还是右子树？

代码中解答：

public class Solution {
    // 成员变量：存储最大深度（替代原数组，无需作为参数传递）
    private int maxDepth = 0;

    public int maxDepth(TreeNode root) {
        // 每次调用前重置成员变量（避免多次调用时残留旧值）
        maxDepth = 0;
        // 调用无参辅助方法，从根节点开始前序遍历（默认深度1）
        preorder(root, 1);
        return maxDepth;
    }

    // 辅助方法：仅2个核心参数（当前节点 + 当前深度），无需传递maxDepth
    private void preorder(TreeNode node, int currentDepth) {
        if (node == null) {
            return; // 递归边界：空节点直接返回
        }

        // 1. 前序核心：先处理当前节点，更新最大深度
        if (currentDepth > maxDepth) {
            maxDepth = currentDepth;
        }

        // 2. 递归遍历左子树（深度+1）
        preorder(node.left, currentDepth + 1);
        // 3. 递归遍历右子树（深度+1）
        preorder(node.right, currentDepth + 1);
    }

其实无论哪种方式遍历都可以解决问题，而为了解决左 / 右子树深度不同，我们只需遍历到比当前节点深赋值加 1 就行，currentDepth 是局部参数：每次递归传递 currentDepth + 1 时，不会修改上层参数值（如根节点的 currentDepth 始终为 1）。

当然这是正确的方法，不过也有更优美的代码。让我们想一想求最大深度也就等价于求树的最大高度，可这又有什么区别呢？关键点就在这里，如果把从树的顶端遍历转化为从树的底部开始遍历，你是不是有新的思路了。

代码如下：

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = maxDepth(root.left);
            int rightHeight = maxDepth(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

图片示例：

return Math.max(leftHeight, rightHeight) + 1; 会直接把当前节点的最大深度返回给父节点，是不是一下就简单多了。

五、核心运用场景总结

1. 深度遍历顺序：

   • 前序遍历：二叉树复制、路径记录、最大深度（自上而下）；

   • 中序遍历：BST 排序 / 验证、有序链表转 BST；

   • 后序遍历：子树计算、二叉树删除、最大深度（自下而上，面试最优）。

2. 最大深度求解：

   • 前序版：需跟踪路径的场景（如接口调用链路监控）；

   • 后序版：算法面试、服务依赖链深度、树形菜单层级计算。