遍历序列构造二叉树的三种经典模式（LeetCode 105/106/889）

106. 从中序与后序遍历构造二叉树

原题链接：LeetCode 106

给定 inorder 和 postorder，无重复，重建二叉树。

示例：

inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出: [3,9,20,null,null,15,7]
inorder = [-1], postorder = [-1]
输出: [-1]

提示与105题类似，数组长度和值范围一致。

思路完全一样，只是根在 postorder 的末尾。因此 index 从后往前移动，并且递归时要先构建右子树再构建左子树（因为后序遍历是 左-右-根，倒过来就是根-右-左）。

代码：

class Solution {
    int index; // 当前在后序中的位置，从末尾开始

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        index = inorder.length - 1;
        return dfs(inorder, postorder, 0, inorder.length - 1);
    }

    public TreeNode dfs(int[] inorder, int[] postorder, int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = 0;
        for (int i = left; i <= right; i++) {
            if (inorder[i] == postorder[index]) {
                mid = i;
                break;
            }
        }
        TreeNode root = new TreeNode(postorder[index]);
        index--;
        // 后序倒序，先处理右子树
        root.right = dfs(inorder, postorder, mid + 1, right);
        root.left = dfs(inorder, postorder, left, mid - 1);
        return root;
    }
}

889. 根据前序与后序遍历构造二叉树

原题链接：LeetCode 889

给定无重复的前序和后序数组，重建二叉树。如果存在多种答案，返回任意一种即可。

示例：

preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出: [1,2,3,4,5,6,7]
preorder = [1], postorder = [1]
输出: [1]

提示：长度 1~30，所有值不同，且是同一棵树的有效遍历。

这题跟前两题的区别在于没有中序序列来明确划分左右子树。所以我们需要在前序中提前找到左子树的根节点，然后在后序中确定左子树的范围。具体做法：

• 前序的第一个元素是整棵树的根。
• 根后面的第一个元素是左子树的根（如果左子树存在）。
• 在后序数组中找到这个左子树根的位置，该位置及之前的所有元素就是左子树的后序序列（因为后序中左子树的所有节点必然先出现，然后是右子树，最后是根）。
• 据此划分出左子树的范围进行递归；剩余部分是右子树的范围（注意要把后序末尾的根节点排除，所以右子树范围是 mid+1 到 right-1）。

还需要处理叶子节点（即当前范围只有一个节点）的情况：如果 left == right，说明这个子树只有一个节点，并且已经在前面作为根 new 出来了，后面没有左子树根可找，直接返回即可，否则 index 会越界。

代码：

class Solution {
    int index = 0; // 前序从 0 开始

    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        return dfs(preorder, postorder, 0, postorder.length - 1);
    }

    public TreeNode dfs(int[] preorder, int[] postorder, int left, int right) {
        if (left > right) return null;
        // 当前前序指针指向的值就是根
        TreeNode root = new TreeNode(preorder[index]);
        index++;
        // 叶子节点：当前范围只剩一个数，且已被 new，后续没有左子树根
        if (left == right) return root;
        // 找左子树根在后序中的位置
        int mid = 0;
        for (int i = left; i <= right; i++) {
            if (postorder[i] == preorder[index]) {
                mid = i;
                break;
            }
        }
        // 左子树范围：left 到 mid
        root.left = dfs(preorder, postorder, left, mid);
        // 右子树范围：mid+1 到 right-1（去掉后序末尾的根）
        root.right = dfs(preorder, postorder, mid + 1, right - 1);
        return root;
    }
}

这三道题其实是一个模板刻出来的。只要搞清楚根的位置和划分左右子树的依据，写起来就很快。105 和 106 基本是镜像，889 稍微绕一点，但核心还是分治。