Middle order and post order traversal to construct binary tree [recursive partition interval and backtracking splicing subtree + similarity and difference between middle post order and middle pre orde

Preface

According to a sequence , You can recursively divide the intervals , Backtracking and splicing subtrees to complete tree generation .
Pre middle order traversal , A node that can determine the root node , One can hold the root node to divide the left and right intervals , Completed the pre task abstractly , So the first middle order can determine a binary search tree . Empathy , The same is true of the middle and later sequence , Do not traverse the root node after the sequence , And the traversal is left and right root , So when the root passes, it is right , So we need to build the right subtree first , Then build the left subtree .

One 、 Middle order and post order traversal to build a binary search tree

Two 、 From top to bottom + Bottom up

//  According to the middle order  +  After the order to build a binary tree .
class BuildTree2 {
    
    /* target： Use post order and middle order traversal to construct binary tree .  Aftereffect ？ All root nodes on the left subtree are obtained from right to left .  Middle order function ？ The right and left subtrees are divided by the root nodes traversed in the following order , Continuous division , Generate a binary tree from bottom to top . */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
    
        // assert  No repeating elements .
        Map<Integer, Integer> m = new HashMap<>();
        //  preparation , Get the root node location quickly , Divide the left and right subtrees .
        for (int i = 0; i < inorder.length; i++) m.put(inorder[i], i);
        //  Building tree 
        idx = postorder.length - 1;
        return buildTree(inorder, postorder, 0, inorder.length - 1, m);
    }

    int idx = 0;

    private TreeNode buildTree(int[] inorder, int[] postorder, int begin, int end, Map<Integer, Integer> m) {
    
        if (begin > end) return null;
        //  Use the root node to divide the left and right subtrees , Root node by preorder[idx] Come to .
        int mid = m.get(postorder[idx--]);
        //  Get recursively generated left and right children .
        //  Be careful , The following traversal is left and right root , So first we get the right subtree , Get the left subtree , This is the difference from the previous sequence traversal location .
        TreeNode right = buildTree(inorder, postorder, mid + 1, end, m);
        TreeNode left = buildTree(inorder, postorder, begin, mid - 1, m);
        //  Generate root node .
        TreeNode root = new TreeNode(inorder[mid]);
        //  Join the left and right subtrees .
        root.left = left;
        root.right = right;
        //  Back to the spliced root Trees .
        return root;
    }

    // Definition for a binary tree node.
    public class TreeNode {
    
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
    
        }

        TreeNode(int val) {
    
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
    
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}

summary

1） Spanning tree foundation , Recursively divide the interval from top to bottom , Join the left and right subtrees from the bottom up .
2） The similarities and differences between the pre middle order traversal spanning tree and the post middle order spanning tree .

reference

[1] LeetCode Middle order and subsequent traversal to build a binary tree
[2] Middle order and pre order traversal to build a binary tree