LeetCode树与二叉树全解析：从基础到高级应用

安全风信子

发布于 2025-11-13 14:07:23

1520

文章被收录于专栏：AI SPPECHAI SPPECH

一、树与二叉树基础

1.1 树的基本概念

树是一种重要的非线性数据结构，它是由n(n≥0)个节点组成的有限集合。当n=0时，称为空树；当n>0时，有一个特定的称为根(Root)的节点，其余节点可分为m(m≥0)个互不相交的有限集合，每个集合本身又是一棵树，称为根的子树。

树的基本术语：

节点：树中的元素，包含数据项及若干指向其子树的分支
节点的度：节点拥有的子树数目
叶子节点：度为0的节点
非叶子节点：度不为0的节点
树的度：树中节点的最大度
节点的层次：从根开始定义，根为第一层，根的子节点为第二层，以此类推
树的高度：树中节点的最大层次
森林：m棵互不相交的树的集合

1.2 二叉树的基本概念

二叉树是一种特殊的树，它的每个节点最多有两个子树，通常称为左子树和右子树。二叉树的子树有左右之分，次序不能颠倒。

二叉树的性质：

在二叉树的第i层上最多有2^(i-1)个节点(i≥1)
深度为k的二叉树最多有2^k - 1个节点(k≥1)
对任何一棵二叉树T，如果其叶子节点数为n0，度为2的节点数为n2，则n0 = n2 + 1

特殊类型的二叉树：

满二叉树：除叶子节点外，每个节点都有两个子节点，且所有叶子节点都在同一层
完全二叉树：除最后一层外，其他层的节点数都达到最大，且最后一层的节点都连续集中在最左边
二叉搜索树：左子树上所有节点的值均小于根节点的值，右子树上所有节点的值均大于根节点的值，且左右子树也分别为二叉搜索树
平衡二叉树：任意节点的左右子树高度差的绝对值不超过1

1.3 二叉树的存储结构

二叉树的存储结构主要有两种：顺序存储结构和链式存储结构。

顺序存储结构：使用一维数组存储二叉树的节点，适用于完全二叉树。对于完全二叉树，若节点的索引为i，则其左子节点的索引为2i，右子节点的索引为2i+1，父节点的索引为i/2（向下取整）。

链式存储结构：每个节点包含数据域和两个指针域，分别指向左子节点和右子节点。Java中通常使用类来实现：

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

二、二叉树的遍历

2.1 深度优先遍历

深度优先遍历是指沿着树的深度遍历树的节点，尽可能深地搜索树的分支。深度优先遍历包括前序遍历、中序遍历和后序遍历三种方式。

2.1.1 前序遍历（LeetCode 144）

题目描述：给你二叉树的根节点 root ，返回它节点值的前序遍历。

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

定义：前序遍历的顺序是根-左-右，即先访问根节点，然后遍历左子树，最后遍历右子树。

递归实现：

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

private void preorder(TreeNode root, List<Integer> result) {
    if (root == null) {
        return;
    }
    // 根-左-右
    result.add(root.val);
    preorder(root.left, result);
    preorder(root.right, result);
}

迭代实现：

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Stack<TreeNode> stack = new Stack<>();
    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;
}

2.1.2 中序遍历（LeetCode 94）

题目描述：给定一个二叉树的根节点 root ，返回它的中序遍历。

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

定义：中序遍历的顺序是左-根-右，即先遍历左子树，然后访问根节点，最后遍历右子树。

递归实现：

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

private void inorder(TreeNode root, List<Integer> result) {
    if (root == null) {
        return;
    }
    // 左-根-右
    inorder(root.left, result);
    result.add(root.val);
    inorder(root.right, result);
}

迭代实现：

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        // 不断将左子节点入栈
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        // 弹出栈顶节点，访问其值，然后处理右子树
        curr = stack.pop();
        result.add(curr.val);
        curr = curr.right;
    }
    return result;
}

2.1.3 后序遍历（LeetCode 145）

题目描述：给你一棵二叉树的根节点 root ，返回其节点值的后序遍历。

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

定义：后序遍历的顺序是左-右-根，即先遍历左子树，然后遍历右子树，最后访问根节点。

递归实现：

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

private void postorder(TreeNode root, List<Integer> result) {
    if (root == null) {
        return;
    }
    // 左-右-根
    postorder(root.left, result);
    postorder(root.right, result);
    result.add(root.val);
}

迭代实现：

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
        return result;
    }
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    stack1.push(root);
    // 使用两个栈，第一个栈用于遍历，第二个栈用于存储结果
    while (!stack1.isEmpty()) {
        TreeNode node = stack1.pop();
        stack2.push(node);
        // 注意先压入左子节点，再压入右子节点
        if (node.left != null) {
            stack1.push(node.left);
        }
        if (node.right != null) {
            stack1.push(node.right);
        }
    }
    // 将第二个栈中的节点依次弹出，得到后序遍历结果
    while (!stack2.isEmpty()) {
        result.add(stack2.pop().val);
    }
    return result;
}

2.2 广度优先遍历

广度优先遍历（BFS）是指从根节点开始，逐层访问树的节点。在二叉树中，广度优先遍历通常指的是层序遍历。

2.2.1 层序遍历（LeetCode 102）

题目描述：给你二叉树的根节点 root ，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。

示例：输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]

解题思路：层序遍历通常使用队列来实现。我们可以使用一个队列来存储当前层的节点，然后逐层处理这些节点。

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;
}

时间复杂度：O(n)，其中n是树中的节点数。每个节点都会被访问一次。 空间复杂度：O(n)，在最坏情况下，队列可能需要存储树中最底层的所有节点，最底层节点数最多为n/2。

三、二叉树的基本操作

3.1 二叉树的高度（LeetCode 104）

题目描述：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

示例：输入：root = [3,9,20,null,null,15,7] 输出：3

解题思路：我们可以使用递归或迭代的方法来计算二叉树的高度。递归方法的基本思想是：二叉树的高度等于其左右子树高度的最大值加1。

递归实现：

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

迭代实现（使用层序遍历）：

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int depth = 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    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;
}

3.2 平衡二叉树（LeetCode 110）

题目描述：给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。

示例：输入：root = [3,9,20,null,null,15,7] 输出：true

解题思路：我们可以使用递归的方法来判断二叉树是否平衡。对于每个节点，我们需要计算其左右子树的高度，并检查高度差是否不超过1。

自顶向下的方法：

public boolean isBalanced(TreeNode root) {
    if (root == null) {
        return true;
    }
    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);
    // 检查当前节点是否平衡，以及左右子树是否平衡
    return Math.abs(leftDepth - rightDepth) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}

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

这种方法的时间复杂度为O(n²)，在最坏情况下（树是一条链），每个节点都会被多次计算高度。

自底向上的方法：

public boolean isBalanced(TreeNode root) {
    return checkHeight(root) != -1;
}

// 如果树平衡，返回其高度；否则返回-1
private int checkHeight(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftHeight = checkHeight(root.left);
    if (leftHeight == -1) {
        return -1; // 左子树不平衡
    }
    int rightHeight = checkHeight(root.right);
    if (rightHeight == -1) {
        return -1; // 右子树不平衡
    }
    if (Math.abs(leftHeight - rightHeight) > 1) {
        return -1; // 当前节点不平衡
    }
    return Math.max(leftHeight, rightHeight) + 1;
}

这种方法的时间复杂度为O(n)，每个节点只需要访问一次。

3.3 对称二叉树（LeetCode 101）

题目描述：给定一个二叉树，检查它是否是镜像对称的。

示例：输入：root = [1,2,2,3,4,4,3] 输出：true

解题思路：我们可以使用递归或迭代的方法来判断二叉树是否对称。对称的二叉树需要满足：根节点的左右子树互为镜像。

递归实现：

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);
}

迭代实现：

public boolean isSymmetric(TreeNode root) {
    if (root == null) {
        return true;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root.left);
    queue.offer(root.right);
    while (!queue.isEmpty()) {
        TreeNode left = queue.poll();
        TreeNode right = queue.poll();
        if (left == null && right == null) {
            continue;
        }
        if (left == null || right == null || left.val != right.val) {
            return false;
        }
        // 将左节点的左子树和右节点的右子树入队
        queue.offer(left.left);
        queue.offer(right.right);
        // 将左节点的右子树和右节点的左子树入队
        queue.offer(left.right);
        queue.offer(right.left);
    }
    return true;
}

3.4 二叉树的最小深度（LeetCode 111）

题目描述：给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

示例：输入：root = [3,9,20,null,null,15,7] 输出：2

解题思路：我们可以使用递归或迭代的方法来计算二叉树的最小深度。需要注意的是，如果树只有一边子树，那么最小深度应该是另一边子树的深度加1。

递归实现：

public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    // 如果左子树为空，返回右子树的最小深度加1
    if (root.left == null) {
        return minDepth(root.right) + 1;
    }
    // 如果右子树为空，返回左子树的最小深度加1
    if (root.right == null) {
        return minDepth(root.left) + 1;
    }
    // 如果左右子树都不为空，返回左右子树最小深度的较小值加1
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}

迭代实现（使用层序遍历）：

public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int depth = 0;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        depth++;
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            // 如果是叶子节点，返回当前深度
            if (node.left == null && node.right == null) {
                return depth;
            }
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }
    return depth;
}

四、二叉搜索树（BST）

4.1 二叉搜索树的基本概念

二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树，它具有以下性质：

左子树上所有节点的值均小于根节点的值
右子树上所有节点的值均大于根节点的值
左右子树也分别为二叉搜索树

二叉搜索树的一个重要特性是：中序遍历二叉搜索树可以得到一个递增的有序序列。

4.2 验证二叉搜索树（LeetCode 98）

题目描述：给定一个二叉树，判断其是否是一个有效的二叉搜索树。

示例：输入：root = [2,1,3] 输出：true

解题思路：我们可以使用递归或迭代的方法来验证二叉搜索树。递归方法的基本思想是：对于每个节点，我们需要检查其值是否在合法的范围内。

递归实现（使用上下界）：

public boolean isValidBST(TreeNode root) {
    return validate(root, null, null);
}

private boolean validate(TreeNode node, Integer lower, Integer upper) {
    if (node == null) {
        return true;
    }
    if ((lower != null && node.val <= lower) || (upper != null && node.val >= upper)) {
        return false;
    }
    // 验证左子树，上界为当前节点的值
    // 验证右子树，下界为当前节点的值
    return validate(node.left, lower, node.val) && validate(node.right, node.val, upper);
}

递归实现（利用中序遍历）：

private Integer prev;

public boolean isValidBST(TreeNode root) {
    prev = null;
    return inorder(root);
}

private boolean inorder(TreeNode node) {
    if (node == null) {
        return true;
    }
    // 先验证左子树
    if (!inorder(node.left)) {
        return false;
    }
    // 验证当前节点的值是否大于前一个节点的值（中序遍历的结果应该是递增的）
    if (prev != null && node.val <= prev) {
        return false;
    }
    prev = node.val;
    // 最后验证右子树
    return inorder(node.right);
}

4.3 二叉搜索树中的搜索（LeetCode 700）

题目描述：给定二叉搜索树（BST）的根节点和一个值。你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在，则返回 NULL。

示例：输入：root = [4,2,7,1,3], val = 2 输出：[2,1,3]

解题思路：利用二叉搜索树的性质，我们可以快速定位目标节点。如果当前节点的值等于目标值，则返回当前节点；如果当前节点的值大于目标值，则在左子树中搜索；如果当前节点的值小于目标值，则在右子树中搜索。

递归实现：

public TreeNode searchBST(TreeNode root, int val) {
    if (root == null || root.val == val) {
        return root;
    }
    if (val < root.val) {
        return searchBST(root.left, val);
    } else {
        return searchBST(root.right, val);
    }
}

迭代实现：

public TreeNode searchBST(TreeNode root, int val) {
    TreeNode curr = root;
    while (curr != null && curr.val != val) {
        if (val < curr.val) {
            curr = curr.left;
        } else {
            curr = curr.right;
        }
    }
    return curr;
}

4.4 二叉搜索树中的插入操作（LeetCode 701）

题目描述：给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

示例：输入：root = [4,2,7,1,3], val = 5 输出：[4,2,7,1,3,5]

解题思路：利用二叉搜索树的性质，我们可以找到合适的位置插入新节点。如果根节点为空，直接返回新节点；否则，根据新值与当前节点值的大小关系，决定在左子树还是右子树中插入新节点。

递归实现：

public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) {
        return new TreeNode(val);
    }
    if (val < root.val) {
        root.left = insertIntoBST(root.left, val);
    } else {
        root.right = insertIntoBST(root.right, val);
    }
    return root;
}

迭代实现：

public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) {
        return new TreeNode(val);
    }
    TreeNode curr = root;
    TreeNode parent = null;
    while (curr != null) {
        parent = curr;
        if (val < curr.val) {
            curr = curr.left;
        } else {
            curr = curr.right;
        }
    }
    if (val < parent.val) {
        parent.left = new TreeNode(val);
    } else {
        parent.right = new TreeNode(val);
    }
    return root;
}

4.5 删除二叉搜索树中的节点（LeetCode 450）

题目描述：给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

示例：输入：root = [5,3,6,2,4,null,7], key = 3 输出：[5,4,6,2,null,null,7] 或 [5,2,6,null,4,null,7]

解题思路：删除二叉搜索树中的节点需要考虑以下几种情况：

如果要删除的节点是叶子节点，直接删除即可
如果要删除的节点只有一个子节点，用子节点替换当前节点
如果要删除的节点有两个子节点，需要找到右子树中的最小节点（或左子树中的最大节点），用它来替换当前节点，然后删除那个最小节点

public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) {
        return null;
    }
    if (key < root.val) {
        // 要删除的节点在左子树中
        root.left = deleteNode(root.left, key);
    } else if (key > root.val) {
        // 要删除的节点在右子树中
        root.right = deleteNode(root.right, key);
    } else {
        // 找到要删除的节点
        // 情况1：叶子节点
        if (root.left == null && root.right == null) {
            return null;
        }
        // 情况2：只有一个子节点
        else if (root.left == null) {
            return root.right;
        }
        else if (root.right == null) {
            return root.left;
        }
        // 情况3：有两个子节点
        // 找到右子树中的最小节点
        TreeNode minNode = findMin(root.right);
        // 用最小节点的值替换当前节点的值
        root.val = minNode.val;
        // 删除右子树中的最小节点
        root.right = deleteNode(root.right, minNode.val);
    }
    return root;
}

private TreeNode findMin(TreeNode node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

五、树的高级应用

5.1 二叉树的最近公共祖先（LeetCode 236）

题目描述：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

示例：输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

解题思路：我们可以使用递归的方法来寻找最近公共祖先。递归的基本思想是：对于当前节点，如果它等于p或q，则返回当前节点；否则，递归地在左右子树中寻找p和q。如果左子树和右子树的递归结果都不为空，说明p和q分别在左右子树中，当前节点就是它们的最近公共祖先；如果只有一个子树的递归结果不为空，返回该结果；如果两个子树的递归结果都为空，返回null。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // 如果根节点为空，或者根节点等于p或q，返回根节点
    if (root == null || root == p || root == q) {
        return root;
    }
    // 递归地在左子树中寻找p和q
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    // 递归地在右子树中寻找p和q
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    // 如果左子树和右子树的递归结果都不为空，说明p和q分别在左右子树中，当前节点就是它们的最近公共祖先
    if (left != null && right != null) {
        return root;
    }
    // 如果只有一个子树的递归结果不为空，返回该结果
    // 如果两个子树的递归结果都为空，返回null
    return left != null ? left : right;
}

5.2 二叉搜索树的最近公共祖先（LeetCode 235）

题目描述：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

示例：输入：root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出：6 解释：节点 2 和节点 8 的最近公共祖先是 6 。

解题思路：利用二叉搜索树的性质，我们可以更高效地寻找最近公共祖先。如果当前节点的值大于p和q的值，说明p和q都在左子树中，我们应该在左子树中寻找最近公共祖先；如果当前节点的值小于p和q的值，说明p和q都在右子树中，我们应该在右子树中寻找最近公共祖先；否则，当前节点就是p和q的最近公共祖先。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) {
        return root;
    }
    // 如果当前节点的值大于p和q的值，在左子树中寻找
    if (root.val > p.val && root.val > q.val) {
        return lowestCommonAncestor(root.left, p, q);
    }
    // 如果当前节点的值小于p和q的值，在右子树中寻找
    if (root.val < p.val && root.val < q.val) {
        return lowestCommonAncestor(root.right, p, q);
    }
    // 否则，当前节点就是最近公共祖先
    return root;
}

5.3 从前序与中序遍历序列构造二叉树（LeetCode 105）

题目描述：根据一棵树的前序遍历与中序遍历构造二叉树。

示例：输入：前序遍历 preorder = [3,9,20,15,7], 中序遍历 inorder = [9,3,15,20,7] 输出：[3,9,20,null,null,15,7]

解题思路：前序遍历的第一个元素是树的根节点，在中序遍历中找到根节点的位置，根节点左边的元素构成左子树，右边的元素构成右子树。然后，我们可以递归地构造左右子树。

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0) {
        return null;
    }
    // 创建一个哈希表，存储中序遍历中每个元素的索引，以便快速查找
    Map<Integer, Integer> inorderMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        inorderMap.put(inorder[i], i);
    }
    return buildTreeHelper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inorderMap);
}

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

5.4 从中序与后序遍历序列构造二叉树（LeetCode 106）

题目描述：根据一棵树的中序遍历与后序遍历构造二叉树。

示例：输入：中序遍历 inorder = [9,3,15,20,7], 后序遍历 postorder = [9,15,7,20,3] 输出：[3,9,20,null,null,15,7]

解题思路：后序遍历的最后一个元素是树的根节点，在中序遍历中找到根节点的位置，根节点左边的元素构成左子树，右边的元素构成右子树。然后，我们可以递归地构造左右子树。

public TreeNode buildTree(int[] inorder, int[] postorder) {
    if (inorder == null || postorder == null || inorder.length == 0 || postorder.length == 0) {
        return null;
    }
    // 创建一个哈希表，存储中序遍历中每个元素的索引，以便快速查找
    Map<Integer, Integer> inorderMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) {
        inorderMap.put(inorder[i], i);
    }
    return buildTreeHelper(inorder, 0, inorder.length - 1,
                         postorder, 0, postorder.length - 1,
                         inorderMap);
}

private TreeNode buildTreeHelper(int[] inorder, int inStart, int inEnd,
                               int[] postorder, int postStart, int postEnd,
                               Map<Integer, Integer> inorderMap) {
    if (inStart > inEnd || postStart > postEnd) {
        return null;
    }
    // 后序遍历的最后一个元素是根节点
    TreeNode root = new TreeNode(postorder[postEnd]);
    // 在中序遍历中找到根节点的位置
    int rootIndex = inorderMap.get(root.val);
    // 计算左子树的大小
    int leftSize = rootIndex - inStart;
    // 递归地构造左子树和右子树
    root.left = buildTreeHelper(inorder, inStart, rootIndex - 1,
                              postorder, postStart, postStart + leftSize - 1,
                              inorderMap);
    root.right = buildTreeHelper(inorder, rootIndex + 1, inEnd,
                               postorder, postStart + leftSize, postEnd - 1,
                               inorderMap);
    return root;
}

六、树的特殊类型

6.1 完全二叉树的节点个数（LeetCode 222）

题目描述：给你一棵完全二叉树的根节点 root ，求出该树的节点个数。

示例：输入：root = [1,2,3,4,5,6] 输出：6

解题思路：对于完全二叉树，我们可以利用其特性来优化计算节点个数的算法。完全二叉树的特点是：除了最后一层外，其他层的节点数都达到最大，且最后一层的节点都连续集中在最左边。

方法一：普通递归

public int countNodes(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return 1 + countNodes(root.left) + countNodes(root.right);
}

这种方法的时间复杂度为O(n)，其中n是树中的节点数。

方法二：利用完全二叉树的特性

public int countNodes(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftHeight = getHeight(root.left);
    int rightHeight = getHeight(root.right);
    // 如果左子树的高度等于右子树的高度，说明左子树是一棵满二叉树
    if (leftHeight == rightHeight) {
        // 左子树的节点数为2^leftHeight - 1，加上根节点，再加上右子树的节点数
        return (1 << leftHeight) + countNodes(root.right);
    } else {
        // 如果左子树的高度大于右子树的高度，说明右子树是一棵满二叉树
        // 右子树的节点数为2^rightHeight - 1，加上根节点，再加上左子树的节点数
        return (1 << rightHeight) + countNodes(root.left);
    }
}

// 计算完全二叉树的高度（从根节点到最左边叶子节点的路径长度）
private int getHeight(TreeNode node) {
    int height = 0;
    while (node != null) {
        height++;
        node = node.left;
    }
    return height;
}

这种方法的时间复杂度为O(log²n)，其中n是树中的节点数。

6.2 平衡二叉树的实现（AVL树）

平衡二叉树（AVL树）是一种特殊的二叉搜索树，它通过旋转操作来保持树的平衡，从而保证树的高度为O(log n)。

AVL树的基本操作包括：插入、删除和旋转。插入和删除操作可能会导致树失去平衡，此时需要通过旋转操作来恢复平衡。

AVL树的节点结构：

public class AVLTreeNode {
    int val;
    int height;
    AVLTreeNode left;
    AVLTreeNode right;
    AVLTreeNode(int val) {
        this.val = val;
        this.height = 1;
    }
}

获取节点的高度：

private int getHeight(AVLTreeNode node) {
    if (node == null) {
        return 0;
    }
    return node.height;
}

计算平衡因子：

private int getBalanceFactor(AVLTreeNode node) {
    if (node == null) {
        return 0;
    }
    return getHeight(node.left) - getHeight(node.right);
}

更新节点的高度：

private void updateHeight(AVLTreeNode node) {
    if (node == null) {
        return;
    }
    node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
}

右旋转：

private AVLTreeNode rightRotate(AVLTreeNode y) {
    AVLTreeNode x = y.left;
    AVLTreeNode T3 = x.right;
    // 执行旋转
    x.right = y;
    y.left = T3;
    // 更新高度
    updateHeight(y);
    updateHeight(x);
    // 返回新的根节点
    return x;
}

左旋转：

private AVLTreeNode leftRotate(AVLTreeNode x) {
    AVLTreeNode y = x.right;
    AVLTreeNode T2 = y.left;
    // 执行旋转
    y.left = x;
    x.right = T2;
    // 更新高度
    updateHeight(x);
    updateHeight(y);
    // 返回新的根节点
    return y;
}

插入操作：

public AVLTreeNode insert(AVLTreeNode root, int val) {
    // 1. 执行标准BST插入
    if (root == null) {
        return new AVLTreeNode(val);
    }
    if (val < root.val) {
        root.left = insert(root.left, val);
    } else if (val > root.val) {
        root.right = insert(root.right, val);
    } else {
        // 值已存在，不做任何操作
        return root;
    }
    // 2. 更新当前节点的高度
    updateHeight(root);
    // 3. 获取平衡因子，检查是否需要旋转
    int balance = getBalanceFactor(root);
    // 4. 如果节点不平衡，执行旋转操作
    // 左左情况
    if (balance > 1 && val < root.left.val) {
        return rightRotate(root);
    }
    // 右右情况
    if (balance < -1 && val > root.right.val) {
        return leftRotate(root);
    }
    // 左右情况
    if (balance > 1 && val > root.left.val) {
        root.left = leftRotate(root.left);
        return rightRotate(root);
    }
    // 右左情况
    if (balance < -1 && val < root.right.val) {
        root.right = rightRotate(root.right);
        return leftRotate(root);
    }
    // 返回未改变的节点指针
    return root;
}

七、树与二叉树的应用场景

7.1 文件系统

文件系统通常使用树结构来组织文件和目录。在文件系统中，每个目录可以包含多个文件和子目录，形成一棵层次分明的树。

7.2 数据库索引

数据库中的索引通常使用B树或B+树来实现。B树和B+树是一种平衡的多路搜索树，它们能够保持数据的排序，并允许快速的查找、插入和删除操作。

7.3 编译器语法树

在编译器中，语法分析阶段会将源代码转换为抽象语法树（AST）。抽象语法树是一种表示程序结构的树，它的每个节点代表一个语法结构，如表达式、语句或声明。

7.4 决策树

决策树是一种基于树结构的分类和回归方法。在决策树中，每个内部节点代表一个属性上的测试，每个分支代表一个测试结果，每个叶节点代表一个类别或回归值。

7.5 网络路由

在计算机网络中，路由协议通常使用树结构来组织网络拓扑。例如，生成树协议（STP）通过在局域网中创建一棵无环的树，来避免数据包在网络中无限循环。

八、树与二叉树的算法技巧总结

8.1 递归与迭代

树的许多操作都可以使用递归或迭代的方法来实现。递归方法通常更加简洁明了，但在处理大规模数据时可能会导致栈溢出；迭代方法通常更加高效，但代码可能会更加复杂。

8.2 深度优先搜索（DFS）与广度优先搜索（BFS）

深度优先搜索和广度优先搜索是树的两种基本遍历方法。深度优先搜索包括前序遍历、中序遍历和后序遍历，通常使用递归或栈来实现；广度优先搜索通常指层序遍历，通常使用队列来实现。

8.3 分治思想

分治思想是解决树问题的一种常用方法。对于许多树问题，我们可以将其分解为对左右子树的相同问题，然后将左右子树的解合并得到原问题的解。

8.4 动态规划

动态规划也可以应用于树问题。例如，在求二叉树的最大路径和（LeetCode 124）等问题中，可以使用动态规划的思想来解决。

8.5 哈希表优化

在一些树问题中，使用哈希表可以优化算法的时间复杂度。例如，在前序与中序遍历序列构造二叉树（LeetCode 105）问题中，使用哈希表可以快速查找中序遍历中根节点的位置，从而将时间复杂度从O(n²)优化到O(n)。

九、面试高频树与二叉树问题

9.1 二叉树的最大路径和（LeetCode 124）

题目描述：路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。路径和是路径中各节点值的总和。给你一个二叉树的根节点 root ，返回其最大路径和。

示例：输入：root = [1,2,3] 输出：6 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

解题思路：我们可以使用递归的方法来解决这个问题。对于每个节点，我们需要计算两种路径和：

以该节点为根的子树的最大路径和（可以包含左右子树）
以该节点为起点的最大路径和（只能包含左子树或右子树中的一个）

private int maxSum = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
    maxPathSumHelper(root);
    return maxSum;
}

private int maxPathSumHelper(TreeNode node) {
    if (node == null) {
        return 0;
    }
    // 递归地计算左右子树的最大路径和（以子节点为起点）
    // 如果子树的最大路径和小于0，我们可以选择不包含该子树
    int leftMax = Math.max(0, maxPathSumHelper(node.left));
    int rightMax = Math.max(0, maxPathSumHelper(node.right));
    // 更新全局最大路径和（以当前节点为根，包含左右子树）
    maxSum = Math.max(maxSum, node.val + leftMax + rightMax);
    // 返回以当前节点为起点的最大路径和（只能包含左子树或右子树中的一个）
    return node.val + Math.max(leftMax, rightMax);
}

9.2 验证二叉树的前序序列化（LeetCode 331）

题目描述：序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。

示例：输入：“9,3,4,#,#,1,#,#,2,#,6,#,#” 输出：true

解题思路：我们可以使用栈来解决这个问题。前序遍历的顺序是根-左-右，我们可以用栈来模拟这个过程。对于每个节点，我们需要为它分配两个位置（左子节点和右子节点），当遇到一个非空节点时，我们消耗一个位置，并分配两个新的位置；当遇到一个空节点时，我们只消耗一个位置。如果在任何时候位置数小于0，或者遍历结束后位置数不为0，则说明序列化是无效的。

public boolean isValidSerialization(String preorder) {
    if (preorder == null || preorder.isEmpty()) {
        return false;
    }
    // 分割字符串
    String[] nodes = preorder.split(",");
    // 初始化栈，栈中存储的是当前节点还需要的子节点数
    Stack<Integer> stack = new Stack<>();
    // 根节点需要两个子节点
    stack.push(1);
    for (String node : nodes) {
        // 如果栈为空，说明没有节点需要子节点，但还有节点未处理，序列化无效
        if (stack.isEmpty()) {
            return false;
        }
        // 消耗一个位置
        int count = stack.pop() - 1;
        if (count > 0) {
            // 如果还有位置，将其重新入栈
            stack.push(count);
        }
        // 如果节点不是空节点，需要为它分配两个子节点的位置
        if (!node.equals("#")) {
            stack.push(2);
        }
    }
    // 遍历结束后，栈应该为空，说明所有节点都找到了对应的位置
    return stack.isEmpty();
}

优化版本（使用计数器代替栈）：

public boolean isValidSerialization(String preorder) {
    if (preorder == null || preorder.isEmpty()) {
        return false;
    }
    // 分割字符串
    String[] nodes = preorder.split(",");
    // diff表示可用位置数（出度-入度）
    int diff = 1;
    for (String node : nodes) {
        // 消耗一个位置
        diff--;
        // 如果可用位置数小于0，说明序列化无效
        if (diff < 0) {
            return false;
        }
        // 如果节点不是空节点，增加两个可用位置
        if (!node.equals("#")) {
            diff += 2;
        }
    }
    // 遍历结束后，可用位置数应该为0
    return diff == 0;
}

9.3 二叉树的序列化与反序列化（LeetCode 297）

题目描述：请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例：输入：root = [1,2,3,null,null,4,5] 输出：[1,2,3,null,null,4,5]

解题思路：我们可以使用层序遍历来序列化和反序列化二叉树。序列化时，我们按照层序遍历的顺序将节点的值转换为字符串，用null表示空节点；反序列化时，我们按照层序遍历的顺序从字符串中恢复二叉树。

// 序列化
public String serialize(TreeNode root) {
    if (root == null) {
        return "";
    }
    StringBuilder sb = new StringBuilder();
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        if (node == null) {
            sb.append("null,");
        } else {
            sb.append(node.val).append(",");
            queue.offer(node.left);
            queue.offer(node.right);
        }
    }
    // 删除最后一个逗号
    sb.deleteCharAt(sb.length() - 1);
    return sb.toString();
}

// 反序列化
public TreeNode deserialize(String data) {
    if (data == null || data.isEmpty()) {
        return null;
    }
    String[] nodes = data.split(",");
    TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int index = 1;
    while (!queue.isEmpty() && index < nodes.length) {
        TreeNode node = queue.poll();
        // 处理左子节点
        if (!nodes[index].equals("null")) {
            node.left = new TreeNode(Integer.parseInt(nodes[index]));
            queue.offer(node.left);
        }
        index++;
        // 处理右子节点
        if (index < nodes.length && !nodes[index].equals("null")) {
            node.right = new TreeNode(Integer.parseInt(nodes[index]));
            queue.offer(node.right);
        }
        index++;
    }
    return root;
}

十、总结与展望

树与二叉树是计算机科学中非常重要的数据结构，它们在算法面试中占据着重要的地位。掌握好树与二叉树的基本概念、性质和操作，对于提高算法能力至关重要。

通过本文的学习，我们了解了树与二叉树的基本概念、性质和存储结构，掌握了二叉树的遍历方法（前序遍历、中序遍历、后序遍历和层序遍历），学习了二叉搜索树的基本操作（验证、搜索、插入和删除），以及树的高级应用（最近公共祖先、根据遍历序列构造二叉树等）。

在解决树与二叉树的问题时，我们需要注意以下几点：

选择合适的遍历方法：根据问题的特点，选择合适的遍历方法（深度优先搜索或广度优先搜索）
递归与迭代的选择：根据问题的规模和要求，选择合适的实现方式（递归或迭代）
利用树的特性：利用二叉搜索树、完全二叉树等特殊类型树的特性，优化算法
分治思想的应用：将复杂的树问题分解为简单的子问题，然后将子问题的解合并得到原问题的解
辅助数据结构的使用：合理使用栈、队列、哈希表等辅助数据结构，优化算法的时间和空间复杂度

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-11-12，如有侵权请联系 cloudcommunity@tencent.com 删除

搜索

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！