[数据结构与算法]根据两种遍历结果求二叉树

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

前序遍历、中序遍历确定二叉树

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

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

        public TreeNode helper(int[] preorder,int preStart,int preEnd,int[] inorder,int inStart,int inEnd){
            if (preStart>preEnd||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<Integer,Integer> map=new HashMap<>();
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            if (inorder.length==0||postorder.length==0)
                return null;
            for (int i=0;i<inorder.length;++i)
                map.put(inorder[i],i);
            return helper(postorder,0,postorder.length-1,inorder,0,inorder.length-1);
        }

        public TreeNode helper(int[] postOrder,int postStart,int postEnd,int[] inOrder,int inStart,int inEnd){
            if (postStart>postEnd||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;
        }
    }