“This is the sixth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

The title

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 duplicated elements in the tree.

For example, given

Order = [9,3,15,20,7] postorder = [9,15,7,20,3]Copy the code

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Their thinking

We know that the form of backward traversal is to traverse the left subtree first, then the right subtree, and finally the root node. The middle order traversal takes the form of first the left subtree, then the root node, and then the right node;

As long as we locate the root node in the middle traversal, we can know the number of nodes in the left and right subtrees respectively. We can find that the last element of the array of post-order traversal represents the root node. Since the lengths of post-order traversal and middle-order traversal of the same subtree are obviously the same, we can locate all the left and right parentheses in the above form in the result of post-order traversal.

In this way, we know the results of post-order traversal and middle-order traversal of the left subtree, as well as the results of post-order traversal and middle-order traversal of the right subtree, and we can construct the left and right subtrees recursively, and then connect the two subtrees to the left and right positions of the root node.

When locating the root node in a middle-order traversal, we can consider using a hash table to help us locate the root node quickly. For each key-value pair in the hash map, the key represents an element (the value of the node), and the value represents its position in the middle-order traversal. The code implementation is as follows:

Code implementation

/** * 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; *} *} */
class Solution {
    // Define the hash table used to locate the root node of the ordinal number group
    public HashMap<Integer, Integer> map = new HashMap();
    int[] post;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        post = postorder;
        TreeNode root = helper(0, inorder.length - 1.0, post.length - 1);
        return root;
    }

        public TreeNode helper(int inStart, int inEnd, int postStart, int postEnd){
        if (inStart > inEnd || postStart > postEnd) return null;
        int val = post[postEnd];
        int rootPos = map.get(val);
        TreeNode node = new TreeNode(val);
        node.left = helper(inStart, rootPos -1 , postStart, postStart + rootPos - inStart -1);
        node.right = helper(rootPos+1, inEnd, postStart + rootPos - inStart, postEnd - 1);
        returnnode; }}Copy the code

The last

Complexity analysis:

  • Time complexity: O(n), where n is the number of nodes in the tree.

  • Space complexity: O(n). We need O(n) space to store the hash table, and O(h) space (where H is the height of the tree) to represent the stack space for recursion. Here h is less than n, so the total space complexity is order n.

Previous articles:

  • Closures are a nice thing to use for data binding
  • Binary tree brush summary: binary tree traversal
  • StoreKit2 smells this good? Yeah, I tried it. It smells good
  • After reading this article, I am no longer afraid of being asked how to construct a binary tree.
  • The game guys are trying to get people to pay again. That’s bad!
  • Take you rolled a netease holding cloud music home | adapter
  • Netease Cloud Music Home Page (3)
  • Netease Cloud Music Home Page (2)
  • Netease Cloud Music Home Page (a)
  • Does the code need comments? Write and you lose
  • I would not study in Codable for a long time. They are for fun
  • IOS handles web data gracefully. Do you really? Why don’t you read this one
  • UICollectionView custom layout! This one is enough

Please drink a cup ☕️ + attention oh ~

  1. After reading, remember to give me a thumbs-up oh, there is 👍 power
  2. Follow the public number – HelloWorld Jie Shao, the first time push new posture

Finally, the creation is not easy, if it is helpful to you, I hope you like and support, what questions can also be discussed in the comments section 😄