对于树的题目，有统一的思考方法，那就是站在树（子树）的顶端根节点root思考。

1. 构建(二叉)树

二叉树的遍历分为:

1. 前序遍历(根节点，左子树节点，右子树节点)；
2. 中序遍历(左子树节点,根节点，右子树节点)；
3. 后序遍历(左子树节点，右子树节点，根节点)；
4. 层次遍历(从上到下，从左到右)；

构建树的过程，就是通过它的遍历序列来确定这棵树。我们知道要想惟一确定二叉树,必须要有中序遍历的序列存在。

重建二叉树的基本思路就是先构造根节点，再构造左子树，接下来构造右子树，其中，构造左子树和右子树是一个子问题，递归处理即可。

因此我们只关心如何构造根节点，以及如何递归构造左子树和右子树。

构造根节点:可以通过前序遍历&后序遍历的特点来快速定位根节点。然后再借助于中序序列的特点，分别构建左子树节点和右子树节点。

105. 从前序与中序遍历序列构造二叉树 - M (opens new window)

字节 - 11,亚马逊 - 8，微软 - 6

106. 从中序与后序遍历序列构造二叉树 - M (opens new window)

字节

---

1.1 前序&中序序列构建二叉树

public class Solution{

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        //处理特殊情况
        if(preorder == null || inorder == null){
            return null;
        }

        int preLen = preoder.length;
        int inLen = inorder.length;
        if(preLen == 0 || inLen == 0){
            return null;
        }

        if(preLen != inLen){
            return null;
        }

        // 进入正题：1. 构建{根节点}
        int rootVal = preorder[0];
        TreeNode root = new TreeNode(rootVal);

        if(preLen == 1){
            return root;
        }

        // 2.在中序遍历的序列中，找到根节点的下标
        int index = 0;
        for(int i = 0; i < inLen; i++){
            if(inorder[i] == rootVal){
                index = i;
                break;
            }
        }

        // 3. 切割这些序列，构建左右子树

        // 这里需要注意一点，因为前序序列的第一个元素是根节点，已经被使用过。所以这里下标从1开始。
        int[] preLeft = Arrays.copyOfRange(preorder,1, index + 1);
        int[] inLeft = Arrays.copyOfRange(inorder,0,index);

        root.left  = buildTree(preLeft,inLeft);

        int[] preRight = Arrays.copyOfRange(preorder,index+1, preLen);
        int[] inRight = Arrays.copyOfRange(inorder,index+1,inLen);

        root.right = buildTree(preRight,inRight);

        return root;
    }
}

1.2 中序&后序序列构建二叉树

1.2.1 解法一

这种解法容易理解，但是性能一般。

public class Solution{

    public TreeNode buildTree(int[] inorder, int[] postorder) {

        if(inorder == null || postorder == null) return null;

        int inLen = inorder.length;
        int postLen = postorder.length;

        if(inLen == 0 || postLen == 0){
            return null;
        }

        if(inLen != postLen){
            return null;
        }

        // 1. 构建根节点
        int rootVal = postorder[postLen-1];
        TreeNode root = new TreeNode(rootVal);
        if(inLen == 1){
            return root;
        }

        // 2. 从{中序序列}中找到根节点下标
        int index = 0;
        for(int i = 0 ; i < inLen; i++){
            if(inorder[i] == rootVal){
                index = i;
                break;
            }
        }

        // 3. 分割序列，构建左右子树

        int[] inLeft = Arrays.copyOfRange(inorder,0,index);
        int[] postLeft = Arrays.copyOfRange(postorder,0,index);

        root.left = buildTree(inLeft,postLeft);

        int[] inRight = Arrays.copyOfRange(inorder,index+1,inLen);
        // 注意这里，同样因为根节点的原因，这里的下标要处理一下
        int[] postRight = Arrays.copyOfRange(postorder,index,postLen-1);

        root.right = buildTree(inRight,postRight);

        return root;
    }

}

总结：Arrays.copyOfRange(arr,from,to) (opens new window) 左闭右开。此方法非常好使。

1.2.2 解法二

此解决性能较高，主要是在递归过程中，省略了上面的重建数组部分。(关于下标部分，遵循的是左闭右开原则)

public class Solution{
    public TreeNode buildTree(int[] inorder, int[] postorder){
        return buildTree(inorder,0,inorder.length,0,postorder.length);
    }

    public TreeNode buildTree(int[] inorder int inLeft,int inRight,int[] postorder,int postLeft, int postRight){
        if(inLeft >= inRight || postLeft >= postRight){
            return null;
        }

        int rootVal = postorder[postRight - 1];
        TreeNode root = new TreeNode(rootVal);

        int index = 0;
        for(index = inLeft; index < inRight; index ++){
            if(inorder[index] == rootVal){
                break;
            }
        }
        // 关于这里的postLeft - inLeft + index 是通过推导得出的。
        root.left = buildTree(inorder,inLeft,index,postorder,postLeft,postLeft - inLeft+index);
        root.right = buildTree(inorder,index+1,inRight,postorder,postLeft-inLeft+index,postRight-1);

        return root;
    }
}

推导过程如图所示：

---