LeetCode OJ 106. Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

相比较通过前序序列和中序序列来构建树的过程，通过后序序列和中序序列来构建树的过程有很大的不同，但是原理是相同的：即在先序或者后序中先找到根节点，然后在中序序列中划分出左子树和右子树，然后递归执行即可。后序序列的根节点在数组的最后，后序序列中接近根节点的是右子树，因此我们在递归执行的时候要先构建右子树然后再构建左子树，而通过先序和中序来构建的话要先构建左子树在构建右子树，因为先序中距离根节点较近的是左子树中的节点。在先序和中序构建树的代码基础上作部分修改即可得到如下代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder.length==0 || postorder.length==0) return null;
        
        TreeNode root = new TreeNode(postorder[postorder.length-1]);
        int i;
        for(i=0; i<inorder.length; i++){    //找到根节点在中序序列中的位置
            if(inorder[i] == postorder[postorder.length-1]) break;
        }
        int[] left, right, npostorder;
        if(i>0){
            left = new int[i];              //左子树中的节点
            System.arraycopy(inorder, 0, left, 0, left.length);
        }else left = new int[0];
        if(inorder.length - i -1 > 0){      //右子树中的节点
            right = new int[inorder.length - i -1];
            System.arraycopy(inorder, i+1, right, 0, right.length);
        }else right = new int[0];
        
        npostorder = new int[postorder.length - 1];//删除根节点
        System.arraycopy(postorder, 0, npostorder, 0, npostorder.length);
        root.right = buildTree(right, npostorder);  //构建右子树
        npostorder = new int[postorder.length - right.length - 1];//删除右子树中节点
        System.arraycopy(postorder, 0, npostorder, 0, npostorder.length);
        root.left = buildTree(left, npostorder);//构建左子树
        return root;
    }
}