LeetCode算法系列 105. 从前序与中序遍历序列构造二叉树

LeetCode算法系列（Java版） 105. 从前序与中序遍历序列构造二叉树
LeetCode算法系列（Java版） 106. 从中序与后序遍历序列构造二叉树

力扣原题

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

根据一棵树的前序遍历与中序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

分治法

二叉树相关的很多问题的解决思路都有分治法的思想在里面。

分治法的思想：把原问题拆解成若干个与原问题结构相同但规模更小的子问题，待子问题解决以后，原问题就得以解决。

解题思路

首先大家肯定有个疑问：为什么有前序遍历和中序遍历的结果，就能定义构造出整个二叉树呢？

先来复习明确前序遍历和中序遍历的含义：

前序遍历的顺序是 根节点->左子树->右子树。

中序遍历的顺序是 左子树->根节点->右子树。
注意：前序遍历的总体的 根节点->左子树 和中序遍历总体的 左子树->根节点 存在部分 重叠之处，这些重叠之处就是我们推理寻找规律的关键所在。

我们通过一个更复杂的例子，来清晰的分析解题思路：

前序遍历=[1,2,4,7,3,5,6,8]
中序遍历=[4,7,2,1,5,3,8,6]

当我们手里已明确得到前序遍历和中序遍历的结果时，能根据二叉树的特性推理得到以下规律:

前序遍历和中序遍历都是同一棵树的遍历结果，两个结果中树的节点定义一致；
前序遍历的第一个数，必然是整个二叉树的根节点，如例子中的1；
如果1是整个二叉树的根节点，中序遍历中的1也是整个二叉树的根节点，他左边[4,7,2]就是左子树，他右边[5,3,8,6]就是右子树；
同一个根节点1下，在前序遍历和中序遍历的结果中，根节点的左子树和右子树的节点个数必然一样，中序遍历的左子树[4,7,2]为3个节点，右子树[5,3,8,6]为4个节点，所以前序遍历的左子树也为3个节点[2,4,7]，右子树也为4个节点[3,5,6,8]；
此时问题已经分治为几个小的相同的问题，显然能作为递归的结构去处理。

首先这个二叉树的根节点为1；
根节点1的左子树，前序遍历结果为[2,4,7]，中序遍历结果为[4,7,2]；
根节点1的右子树，前序遍历结果为[3,5,6,8]，中序遍历结果为[5,3,8,6]；

如何划分数组的界限，我们可以定义不同的下标（游标）来实现编码。前序遍历左右preLeft、preRight,中序遍历左右inLeft、inRight。

代码实现

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int preLen = preorder.length;
        int inLen = inorder.length;
        if (preLen != inLen) {
            throw new RuntimeException("Incorrect input data.");
        }
        return buildTree(preorder, 0, preLen - 1, inorder, 0, inLen - 1);
    }


    /**
     * 使用数组 preorder 在索引区间 [preLeft, preRight] 中的所有元素
     * 和数组 inorder 在索引区间 [inLeft, inRight] 中的所有元素构造二叉树
     *
     * @param preorder 二叉树前序遍历结果
     * @param preLeft  二叉树前序遍历结果的左边界
     * @param preRight 二叉树前序遍历结果的右边界
     * @param inorder  二叉树后序遍历结果
     * @param inLeft   二叉树后序遍历结果的左边界
     * @param inRight  二叉树后序遍历结果的右边界
     * @return 二叉树的根结点
     */
    private TreeNode buildTree(int[] preorder, int preLeft, int preRight,
                               int[] inorder, int inLeft, int inRight) {
        // 因为是递归调用的方法，先写递归终止条件
        if (preLeft > preRight || inLeft > inRight) {
            return null;
        }
        // 先序遍历的起点元素很重要
        int pivot = preorder[preLeft];
        TreeNode root = new TreeNode(pivot);
        int pivotIndex = inLeft;
        // 严格上说还要做数组下标是否越界的判断 pivotIndex < inRight
        while (inorder[pivotIndex] != pivot) {
            pivotIndex++;
        }
        root.left = buildTree(preorder, preLeft + 1, pivotIndex - inLeft + preLeft,
                inorder, inLeft, pivotIndex - 1);
        root.right = buildTree(preorder, pivotIndex - inLeft + preLeft + 1, preRight,
                inorder, pivotIndex + 1, inRight);
        return root;
    }
}