树与二叉树基础

树是一种非线性的层次数据结构，广泛应用于文件系统、数据库索引、编译器等场景。与线性结构不同，树形结构可以表示一对多的关系。

树的基本概念

定义

树是由 n（n ≥ 0）个节点组成的有限集合：

n = 0 时，称为空树
n > 0 时，有一个特殊的节点称为根节点
其余节点分为 m（m > 0）个互不相交的有限集合，每个集合又是一棵树

基本术语

术语	定义
节点	树中的基本单位
根节点	没有父节点的节点
叶子节点	没有子节点的节点
内部节点	有子节点的非根节点
父节点	直接上级节点
子节点	直接下级节点
兄弟节点	具有相同父节点的节点
节点的度	子节点的个数
树的度	所有节点度的最大值
节点的层次	从根到该节点的路径长度（根节点为第 1 层）
树的高度	节点的最大层次
深度	从根到该节点的边数

树与线性结构的区别

特性	线性结构	树形结构
元素关系	一对一	一对多
首元素	无前驱	根节点无父节点
尾元素	无后继	叶子节点无子节点
中间元素	一个前驱一个后继	一个父节点多个子节点

二叉树

二叉树是每个节点最多有两个子节点的树。二叉树是最重要的树形结构，因为很多树的问题都可以转化为二叉树问题来解决。

二叉树的性质

第 i 层最多有 $2^{i-1}$ 个节点
深度为 k 的二叉树最多有 $2^k - 1$ 个节点
对于任意二叉树，叶子节点数 = 度为 2 的节点数 + 1

性质 3 的推导：

设 $n_0$ 为叶子节点数， $n_1$ 为度为 1 的节点数， $n_2$ 为度为 2 的节点数。

节点总数 $n = n_0 + n_1 + n_2$
边的总数 = $n - 1$ （除根节点外，每个节点有一条边指向它）
边的总数也等于 $n_1 + 2n_2$ （度为 1 的节点贡献 1 条边，度为 2 的节点贡献 2 条边）

所以： $n_0 + n_1 + n_2 - 1 = n_1 + 2n_2$

化简得： $n_0 = n_2 + 1$

二叉树的实现

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
    }
    
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

二叉树的遍历

遍历是二叉树最基本的操作，按照访问根节点的顺序分为四种方式。

前序遍历（根-左-右）

先访问根节点，再遍历左子树，最后遍历右子树。

// 递归实现
public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    preorder(root, result);
    return result;
}

private void preorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    
    result.add(node.val);           // 访问根
    preorder(node.left, result);    // 遍历左子树
    preorder(node.right, result);   // 遍历右子树
}

// 迭代实现
public List<Integer> preorderTraversalIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;
    
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        
        // 先右后左，保证左子树先遍历
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    
    return result;
}

为什么迭代时要先右后左？

因为栈是后进先出的，要保证左子树先遍历，就要让左子节点后入栈。

中序遍历（左-根-右）

先遍历左子树，再访问根节点，最后遍历右子树。

// 递归实现
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    inorder(root, result);
    return result;
}

private void inorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    
    inorder(node.left, result);     // 遍历左子树
    result.add(node.val);           // 访问根
    inorder(node.right, result);    // 遍历右子树
}

// 迭代实现
public List<Integer> inorderTraversalIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode current = root;
    
    while (current != null || !stack.isEmpty()) {
        // 先遍历到最左边的节点
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        
        // 访问节点
        current = stack.pop();
        result.add(current.val);
        
        // 转向右子树
        current = current.right;
    }
    
    return result;
}

中序遍历的特殊意义：对于二叉搜索树，中序遍历可以得到有序序列。

后序遍历（左-右-根）

先遍历左子树，再遍历右子树，最后访问根节点。

// 递归实现
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    postorder(root, result);
    return result;
}

private void postorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    
    postorder(node.left, result);   // 遍历左子树
    postorder(node.right, result);  // 遍历右子树
    result.add(node.val);           // 访问根
}

// 迭代实现（使用前序遍历的逆序）
public List<Integer> postorderTraversalIterative(TreeNode root) {
    LinkedList<Integer> result = new LinkedList<>();
    if (root == null) return result;
    
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.addFirst(node.val);  // 头插法
        
        // 先左后右
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    
    return result;
}

后序遍历的应用：删除二叉树时需要先删除子树再删除根节点，计算目录大小等。

层序遍历

按层次从上到下、从左到右遍历。

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> level = new ArrayList<>();
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        
        result.add(level);
    }
    
    return result;
}

层序遍历的特点：使用 BFS 实现，适合处理需要按层处理的问题。

遍历方式对比

遍历方式	顺序	递归实现	迭代实现	典型应用
前序	根-左-右	简单	栈	复制树、前缀表达式
中序	左-根-右	简单	栈	BST 排序、中缀表达式
后序	左-右-根	简单	栈	删除树、后缀表达式、计算目录大小
层序	按层	不适用	队列	按层处理、最短路径

特殊二叉树

满二叉树

所有叶子节点都在同一层，且每个内部节点都有两个子节点。

满二叉树的特点：

第 i 层有 $2^{i-1}$ 个节点
深度为 k 的满二叉树有 $2^k - 1$ 个节点
叶子节点都在最后一层

完全二叉树

除了最后一层，其他层都是满的，最后一层从左到右排列。

完全二叉树的数组表示：

完全二叉树可以用数组高效存储。对于索引 i（从 0 开始）：

父节点索引： $(i - 1) / 2$
左子节点索引： $2i + 1$
右子节点索引： $2i + 2$

public class ArrayBinaryTree {
    private int[] data;
    
    public ArrayBinaryTree(int[] data) {
        this.data = data;
    }
    
    public int parent(int i) {
        return (i - 1) / 2;
    }
    
    public int leftChild(int i) {
        return 2 * i + 1;
    }
    
    public int rightChild(int i) {
        return 2 * i + 2;
    }
}

数组表示的优点：

空间紧凑，没有指针开销
可以快速定位父子节点
堆就是一种用数组存储的完全二叉树

二叉搜索树 (BST)

二叉搜索树是一种特殊的二叉树，满足以下性质：

左子树所有节点的值 < 根节点的值
右子树所有节点的值 > 根节点的值
左右子树也分别是二叉搜索树

详见二叉搜索树章节。

平衡二叉树 (AVL)

平衡二叉树是一种特殊的二叉搜索树，任何节点的两个子树的高度差不超过 1。详见二叉搜索树章节。

经典二叉树问题

1. 二叉树的最大深度

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

解释：树的深度 = max(左子树深度, 右子树深度) + 1

2. 翻转二叉树

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    
    // 交换左右子树
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    
    // 递归翻转子树
    invertTree(root.left);
    invertTree(root.right);
    
    return root;
}

3. 对称二叉树

判断二叉树是否是自己的镜像。

public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
}

private boolean isMirror(TreeNode left, TreeNode right) {
    if (left == null && right == null) return true;
    if (left == null || right == null) return false;
    
    return left.val == right.val &&
           isMirror(left.left, right.right) &&
           isMirror(left.right, right.left);
}

解释：对称意味着左子树和右子树互为镜像。比较时，左子树的左节点应该等于右子树的右节点。

4. 二叉树的最近公共祖先

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // 基准情况
    if (root == null || root == p || root == q) {
        return root;
    }
    
    // 在左右子树中查找
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    
    if (left != null && right != null) {
        return root;  // p 和 q 分别在左右子树
    }
    
    return left != null ? left : right;
}

解释：

如果 p 和 q 在 root 的两侧，则 root 是 LCA
如果 p 和 q 在同一侧，则在该侧继续查找

5. 从前序与中序遍历构造二叉树

public TreeNode buildTree(int[] preorder, int[] inorder) {
    // 构建中序遍历的索引映射
    Map<Integer, Integer> inorderMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        inorderMap.put(inorder[i], i);
    }
    
    return build(preorder, 0, preorder.length - 1, 
                 inorder, 0, inorder.length - 1, inorderMap);
}

private TreeNode build(int[] preorder, int preStart, int preEnd,
                       int[] inorder, int inStart, int inEnd,
                       Map<Integer, Integer> inorderMap) {
    if (preStart > preEnd || inStart > inEnd) {
        return null;
    }
    
    // 前序遍历的第一个元素是根节点
    int rootVal = preorder[preStart];
    TreeNode root = new TreeNode(rootVal);
    
    // 在中序遍历中找到根节点的位置
    int inRoot = inorderMap.get(rootVal);
    int leftSize = inRoot - inStart;
    
    // 递归构建左右子树
    root.left = build(preorder, preStart + 1, preStart + leftSize,
                      inorder, inStart, inRoot - 1, inorderMap);
    root.right = build(preorder, preStart + leftSize + 1, preEnd,
                       inorder, inRoot + 1, inEnd, inorderMap);
    
    return root;
}

解释：

前序遍历：根 -> 左 -> 右，第一个元素是根
中序遍历：左 -> 根 -> 右，可以确定左右子树的范围

6. 路径总和

判断是否存在从根到叶子的路径，使得路径上所有节点值之和等于目标值。

public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    
    // 到达叶子节点
    if (root.left == null && root.right == null) {
        return root.val == targetSum;
    }
    
    // 递归检查子树
    return hasPathSum(root.left, targetSum - root.val) ||
           hasPathSum(root.right, targetSum - root.val);
}

7. 二叉树的直径

二叉树的直径是任意两个节点之间的最长路径长度。

private int maxDiameter = 0;

public int diameterOfBinaryTree(TreeNode root) {
    maxDiameter = 0;
    depth(root);
    return maxDiameter;
}

private int depth(TreeNode node) {
    if (node == null) return 0;
    
    int leftDepth = depth(node.left);
    int rightDepth = depth(node.right);
    
    // 更新最大直径
    maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
    
    return 1 + Math.max(leftDepth, rightDepth);
}

解释：直径可能不经过根节点，需要在计算深度的同时更新最大直径。

小结

本章我们学习了：

树的基本概念：节点、根、叶子、层次、高度等
二叉树遍历：前序、中序、后序、层序
特殊二叉树：满二叉树、完全二叉树、BST、AVL
经典问题：最大深度、翻转、对称、LCA、构造二叉树、路径问题

二叉树是树形结构的基础，掌握二叉树的遍历和基本操作是解决树问题的关键。

练习

LeetCode 104：二叉树的最大深度
LeetCode 226：翻转二叉树
LeetCode 101：对称二叉树
LeetCode 236：二叉树的最近公共祖先
LeetCode 105：从前序与中序遍历序列构造二叉树
LeetCode 98：验证二叉搜索树
LeetCode 102：二叉树的层序遍历
LeetCode 112：路径总和
LeetCode 543：二叉树的直径
LeetCode 124：二叉树中的最大路径和

树的基本概念​

定义​

基本术语​

树与线性结构的区别​

二叉树​

二叉树的性质​

二叉树的实现​

二叉树的遍历​

前序遍历（根-左-右）​

中序遍历（左-根-右）​

后序遍历（左-右-根）​

层序遍历​

遍历方式对比​

特殊二叉树​

满二叉树​

完全二叉树​

二叉搜索树 (BST)​

平衡二叉树 (AVL)​

经典二叉树问题​

1. 二叉树的最大深度​

2. 翻转二叉树​

3. 对称二叉树​

4. 二叉树的最近公共祖先​

5. 从前序与中序遍历构造二叉树​

6. 路径总和​

7. 二叉树的直径​

小结​

练习​