根据两种遍历结果求二叉树

要确定一个二叉树，必须知道中序遍历，然后再知道前序遍历和后序遍历一种即可，有前序和后序两种遍历结果无法确定二叉树。

前序遍历的第一个是根节点，根据根节点到中序遍历就能得到左右子树的划分，我们利用这个规则不断得到当前的根节点、左右子树，进行遍历。

class Solution {
		public class TreeNode {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int x) { val = x; }
        }
        Map map=new HashMap<>();
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            if (preorder.length==0||inorder.length==0)
                return null;
            for (int i=0;ipreEnd||inStart>inEnd)
                return null;
            TreeNode node=new TreeNode(preorder[preStart]);
            int pos=map.get(node.val);
            node.left=helper(preorder,preStart+1,preStart+pos-inStart,inorder,inStart,pos-1);
            node.right=helper(preorder,preStart+pos-inStart+1,preEnd,inorder,pos+1,inEnd);
            return node;
        }
    }

后序遍历的最后一个是根节点，根据根节点到中序遍历就能得到左右子树的划分，我们利用这个规则不断得到当前的根节点、左右子树，进行遍历。

class Solution {
		public class TreeNode {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int x) { val = x; }
        }
        Map map=new HashMap<>();
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            if (inorder.length==0||postorder.length==0)
                return null;
            for (int i=0;ipostEnd||inStart>inEnd)
                return null;
            int pos=map.get(postOrder[postEnd]);
            TreeNode node=new TreeNode(postOrder[postEnd]);
            node.left=helper(postOrder,postStart,postStart+pos-inStart-1,inOrder,inStart,pos-1);
            node.right=helper(postOrder,postStart+pos-inStart,postEnd-1,inOrder,pos+1,inEnd);
            return node;
        }
    }