LeetCode 前序 + 中序、中序 + 后序、前序 + 后序遍历构造二叉树

注意: 给 root 左右节点赋值的顺序要根据先序还是后序遍历来调整，下面第二题也就是这里做出了调整。

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

原题链接

题目描述

给定两个整数数组 inorder 和 postorder：

• inorder 是同一棵树的 中序遍历 序列。
• postorder 是同一棵树的 后序遍历 序列。

请根据这两个数组 构造 出该二叉树，并返回其根节点。

示例展示

示例 1:

输入:
inorder = [9, 3, 15, 20, 7], postorder = [9, 15, 7, 20, 3]

示例 2:

输入:
inorder = [-1], postorder = [-1]

输出:
[-1]

提示条件

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• -3000 <= inorder[i], postorder[i] <= 3000
• inorder 和 postorder 都由 不同 的值组成。
• postorder 中的每一个值都在 inorder 中。
• inorder 保证是树的中序遍历序列。
• postorder 保证是树的后序遍历序列。

解题思路

这题跟上题思路完全一样，由于前序和后序遍历具有对称性，因此代码也是复用的。同样是根据后序遍历来找出中序遍历中的根节点，直接上代码。

代码

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    //记录 postorder 走到哪里了
    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;
    }
}

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

原题链接

题目描述

给定两个整数数组 preorder 和 postorder：

• preorder 是具有 无重复 值的二叉树的 前序遍历 序列。
• postorder 是同一棵树的 后序遍历 序列。

请根据这两个数组 重构 出该二叉树，并返回其根节点。如果存在多个答案，您可以返回其中 任何一个。

示例展示

示例 1:

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

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

示例 2:

输入:
preorder = [1], postorder = [1]

输出:
[1]

提示条件

• 1 <= preorder.length <= 30
• 1 <= preorder[i] <= preorder.length
• preorder 中所有值都 不同。
• postorder.length == preorder.length
• 1 <= postorder[i] <= preorder.length
• postorder 中所有值都 不同。
• 保证 preorder 和 postorder 是同一棵二叉树的有效遍历序列。

解题思路

这题和前两题略有不同，前两题可以根据中序遍历来区分左右子树，但是这题并没有明确的中间节点可以用，因此不能像前两题一样到下一层递归的时候再找'接班人'，要提前去找好。不同点就在这里，其余的还是模版代码。

代码

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;
        // 1. 取出当前前序指针指向的值作为根
        TreeNode root = new TreeNode(preorder[index]);
        index++;
        // 消耗当前根
        // 【核心特殊点 1】：叶子检查
        // 如果 left == right，说明当前范围就这一个数，且已经被 new 过了，
        // 后面已经没有'左子树根'可以找了，必须直接返回，否则 index 会越界。
        if (left == right) return root;
        // 2. 【核心特殊点 2】：找'接班人'
        // 此时 index 已经指向了下一个数，它是【左子树的根】
        // 我们去后序数组里找这个'左根'的位置 mid
        int mid = 0;
        for (int i = left; i <= right; i++) {
            if (postorder[i] == preorder[index]) {
                mid = i;
                break;
            }
        }
        // 3. 划分边界
        // 左子树：从 left 到 mid（后序中左子树根是左侧部分的最后一个，所以含 mid）
        root.left = dfs(preorder, postorder, left, mid);
        // 右子树：从 mid+1 到 right-1（必须减 1 是因为要把后序数组末尾的当前根踢出去）
        root.right = dfs(preorder, postorder, mid + 1, right - 1);
        return root;
    }
}