题解 | #二叉搜索树的后序遍历序列#

{java}递归思路：

1、前序:序列的第一个值一定是整个树的根节点；
2、后续:根节点左边的值全部的都是在树的左子节点这一边，根节点右边的值都在树的右子节点这一边；
3、根据1和2可以判断树的根节点并将左右子树分开；
4、左右子树同样符合1、2两点，将左右子序列递归即可；

import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        if(pre.length == 0) return null;
        if(pre.length == 1) return new TreeNode(pre[0]);
        int index = 0;
        for (; index < vin.length; index++){
            if(vin[index] == pre[0] ){
                break;
            }
        }
        TreeNode head  = new TreeNode(pre[0]);
        head.left = reConstructBinaryTree(
                Arrays.copyOfRange(pre,1,index + 1),
                Arrays.copyOfRange(vin,0,index)
        );

        head.right = reConstructBinaryTree(
                Arrays.copyOfRange(pre,index + 1,pre.length),
                Arrays.copyOfRange(vin,index + 1,vin.length)
        );
        return head;
    }
}