【Golang Theme learning Month 】 Brushing questions is much better than playing games. The sense of achievement is getting stronger and stronger. I insist on brushing one question every day, exercising 30 minutes every day, waiting for 8-block abs and waiting for big factory offer.

😄


  \color{red}{~}

I believe that if you encounter this problem in the interview, logical, correct expression, tear

There should be more than a few candidates.

Unfamiliar to the tree friend, can see the front of the basic training problem oh!

  • Sequential traversal in a binary tree – iteration, recursion

  • Binary tree before sequential traversal – iteration, recursion

  • Binary tree after sequential traversal – iteration, recursion

  • Sequence traversal of binary tree – iteration, recursion

  • Maximum depth of binary tree – iteration, recursion

  • Symmetric binary tree of binary tree – iteration, recursion

  • Binary tree path summation | Go theme month – iteration, recursion

Leecode 106. Construct binary trees by traversing sequences in middle and rear order

The binary tree is constructed according to the middle-order traversal and post-order traversal of a tree.

Note:

You can assume that there are no repeating elements in the tree.

For example, given

Inorder = [9,3,15,20,7]

Postorder = [9,15,7,20,3]

Return the following binary tree:

Reference code

Define a tree

Struct {* Val int Left *TreeNode // Left * Right *TreeNode // right node *} */Copy the code

GO language version of recursion

  1. You know, this is a tree, it’s just represented as an array

Let’s take this tree as an example

Key points:

A sequential traversal determines the root node

Middle order traversal determines the left and right nodes. In middle order traversal, the root node is found. The left is the left subtree, and the right is the right subtree

And then we recursively continue to find the root in the left subtree, and the left subtree of the left subtree

Same thing with the right subtree.

func buildTree(inorder []int, postorder []int) *TreeNode {
    idxMap := map[int]int{}
    for i, v := range inorder {
        idxMap[v] = i
    }
    var build func(int.int) *TreeNode
    build = func(inorderLeft, inorderRight int) *TreeNode {
        // There are no remaining nodes
        if inorderLeft > inorderRight {
            return nil
        }

        // The last element of the sequential traversal is the root node of the current subtree
        val := postorder[len(postorder)- 1]
        postorder = postorder[:len(postorder)- 1]
        root := &TreeNode{Val: val}

        // Divide middle traversal into two subtrees according to val's position in middle traversal
        // Since we take the element from the end of the sequence each time, we traverse the right subtree first and then the left subtree
        inorderRootIndex := idxMap[val]
        root.Right = build(inorderRootIndex+1, inorderRight)
        root.Left = build(inorderLeft, inorderRootIndex- 1)
        return root
    }
    return build(0.len(inorder)- 1)}Copy the code

Java version

 For example, if inorder = [9,3,15,20,7] * postorder = [9,15,7,20,3] * * 3 * / \ * 9 20 * / \ * 15 7 * Key points: 1 The left and right subtrees * 2 of the middle order are distinguished by the roots. The left node recurses (0~ root-1, 0~ back-ordered left + left-subtree -1) * 3. The right node recurses (left-subtree +1~ middle-ordered right, back-ordered left + left-subtree ~ back-ordered right-1) * */
    private static int[] inorder = {15.9.12.3.15.20.7 }; // Determine the left and right nodes
    private static int[] postorder = { 15.12.9.15.7.20.3 }; // Determine the root node
    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        TreeNode root = create(inorder, postorder, 0, inorder.length - 1.0, postorder.length - 1);
        return root;
    }
    private static TreeNode create(int[] inorder, int[] postorder, int inLeft, int inRight, int postLeft, int postRight) {
        if(postLeft > postRight){
            return null;   // return to 15,null,null
        }
        TreeNode treeNode = new TreeNode(postorder[postRight]); The root node is the ordinal number 9 and 14. The root is 15
        int k = 0;
        for(int i = inLeft; i <= inRight; i++){ // 2
            if(inorder[i] == postorder[postRight]){ // 3. If the value in the data = root
                k = i;  // 4. The root subscript is assigned to k = 3
                break; }}int numLeft = k - inLeft; (length of left subtree = 3) Find the root node in the middle order traversal. The left is the left subtree and the right is the right subtree 12.1
        The left node recursion (0~ root-1, 0~ back-order left + left subtree -1) determines the range of the left subtree traversed in the middle order, 0~2, 13. 0~1-1, 0~0+1-1
        The range of the left subtree is 0~2, so the range of the left subtree in the post-ordinal group is 0~2, and the value of the subtree is 9
        // 8.postLeft + numLeft - 1 19. Back in September, null, null
        treeNode.left = create(inorder, postorder, inLeft, k - 1, postLeft, postLeft + numLeft - 1);
        The left subtree is 15,null,null, the length of the left subtree is 0, so to find the right node of the left subtree: return
        treeNode.right = create(inorder, postorder, k + 1, inRight, postLeft + numLeft, postRight - 1);  // 20 returns to 9,15,null continues to find the root node of the left subtree 12
        return treeNode; // 18. Execute this step
    }



Copy the code

Thank you for reading this, if this article is well written and if you feel there is something to it

Ask for a thumbs up 👍 ask for attention ❤️ ask for share 👥 for 8 abs I really very useful!!

If there are any mistakes in this blog, please comment, thank you very much! ❤ ️ ❤ ️ ❤ ️ ❤ ️