Leetcode brush - structure binary tree (105. Once upon a time sequence and the sequence structure binary tree traversal sequence, 106. From the sequence with the sequence structure binary tree travers

105. 从前序与中序遍历序列构造二叉树

题目：从前序与中序遍历序列构造二叉树
First of all, you need to understand some concepts of preorder and inorder traversal

Take the example in the title,Construct from the first one in the preorder,选择3,Found in midorder3,3The left one is the node3The contents of the left subtree,3On the right is the node3The contents of the right subtree,So in the middle sequence3The number on the left is the length of the left subtree,在中序中3The number on the right is the length of the right subtree,这里就需要用mapWrite down the correspondence between the value and the index for easy checking（能用mapbecause there are no repeating elements）.显然,Since preorder traversal starts from the left,So calculate the length of the left subtree,当前的下标+长度,The one before this is on the left subtree,The ones after that are on the right subtree.
下面代码：

	Map<Integer, Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    
        map = new HashMap<>(inorder.length);
        //Record the correspondence between in-order traversal values ​​and subscripts
        for (int i = 0; i < inorder.length; i++) {
    
            map.put(inorder[i], i);
        }
        TreeNode res = build( 0, inorder.length - 1,0, preorder, inorder);
        return res;
    }
    //有返回值,Because the splicing tree is used
    //The methods in the method body are only available at the current moment,不是全局的
    private  TreeNode build( int leftPre, int rightPre,int leftIn, int[] preorder, int[] inorder) {
    
        //After determining the left subtree,得到左子树的长度,Values ​​that exceed the bounds indicate that there are no subtrees left.
        if(leftPre>rightPre){
    
            return null;
        }
        //根节点的值
        int rootVal = preorder[leftPre];
        TreeNode root = new TreeNode(rootVal);
        //The position of the current node in the inorder sequence
        int indexInOrder = map.get(rootVal);
        //左子树的长度
        int leftLen = indexInOrder-leftIn;
        //leftPre：The position of the current value in the preorder
        //rightPre：The position where the current value is the largest in the preorder
        //leftIn：inorderthe left border in （Used to determine length）
        //When exploring the left subtree,from the left of the current node,Start looking for the first one in the pre-order
        root.left= build(leftPre+1, leftPre+leftLen, leftIn , preorder, inorder);
        //explore the right subtree
        root.right= build(leftPre+leftLen+1, rightPre, indexInOrder+1 , preorder, inorder);
        return root;
    }

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

题目：106. 从中序与后序遍历序列构造二叉树
Post-order traversal is done：从最后一个开始,Each time as the root node,But the right subtree is constructed first.
其余几乎一模一样,But this is the right border to be set here.

public TreeNode buildTree(int[] inorder, int[] postorder) {
    
        Map<Integer, Integer> map = new HashMap<>(inorder.length);
        for (int i = 0; i < inorder.length; i++) {
    
            map.put(inorder[i], i);
        }
        TreeNode res = build2( 0, inorder.length - 1,inorder.length - 1, postorder, inorder, map);
        return res;
    }

    private static TreeNode build2( int leftPre, int rightPre,int rightIn, int[] postorder, int[] inorder, Map<Integer, Integer> map) {
    
        //After determining the left subtree,得到左子树的长度
        if(leftPre>rightPre){
    
            return null;
        }
        //根节点的值
        int rootVal = postorder[rightPre];
        TreeNode root = new TreeNode(rootVal);
        //The position of the current node in the inorder sequence
        int indexInOrder = map.get(rootVal);
        //右子树的长度
        int rightLen = rightIn-indexInOrder;
        //rightIn为啥是-1,Because it is from right to left
         root.right= build2(rightPre-rightLen, rightPre-1, rightIn , postorder, inorder, map);
        root.left= build2(leftPre, rightPre-rightLen-1, indexInOrder-1 , postorder, inorder, map);
        return root;
    }