LC106. 从中序与后序遍历序列构造二叉树

参考：代码随想录?

class Solution {
    Map<Integer,Integer> map ;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for(int i= 0 ; i < inorder.length; i ++){
            map.put(inorder[i],i);
        }

        return findNode(inorder,0,inorder.length-1,
                        postorder,0,postorder.length-1);
    }


    public TreeNode findNode(
            int[] inorder, int inBegin, int inEnd, 
            int[] postorder, int postBegin, int postEnd)
    {
            // 左闭右闭的写法
            if(inBegin > inEnd || postBegin > postEnd){
                return null;
            }

            int rootIndex = map.get(postorder[postEnd]);
            TreeNode root = new TreeNode(inorder[rootIndex]);


            int lenOfLeft = rootIndex - inBegin;

            root.left = findNode(inorder,inBegin,rootIndex-1,
                    postorder,postBegin,postBegin+lenOfLeft-1);

            root.right = findNode(inorder,rootIndex+1,inEnd,
                    postorder,postBegin+lenOfLeft,postEnd-1);
            return root;
    }
}