“This is the 25th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

preface

In question 106 of Li Button, the binary tree is constructed from middle-order and back-order traversal sequences as follows:

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

A, thinking

Restore the binary tree using middle-order and post-order traversal. If you want to build a binary tree by traversing a sequence of preorder and middle order, you can find a binary tree by traversing a sequence of preorder and middle order

We know that middle-order traversal and post-order traversal have the following characteristics:

  • Middle order traversal: firstLeft subtree nodeAgain,The root nodeAnd, finally,Right subtree node
  • Backorder traversal: firstLeft subtree nodeAgain,Right subtree nodeAnd, finally,The root node

If I ask you what is the root of a binary tree? You know what?

Obviously, the root of the binary tree is the last element in the sequence. What is the root of the subtree? This depends on the starting position of the current subtree and the number of nodes. Continue to look at the graphic analysis below.

Graphic algorithm

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

  1. Identify the first root noderoot1, is obviously the last node of the post-traversal

  1. Then find the position of the root node in the middle order traversal to determine the left subtreeleft1And right subtreeright1. As shown below:

  1. Let’s confirm the root node of the left subtree left1

    Because the root node root1 is at position 2 in the middle-order traversal, the right subtree has three nodes. So the root of left1 is root1 moved forward by 4 Spaces (to remove itself)

  1. Reconfirm the right subtreeright1The root node of theroot1Before moving1Lattice. (Since subsequent traversals are left and right roots, the root node is preceded by the last node of the right subtree, which is the root node of the right subtree.)

  1. Now that we’ve found all the root nodes, it’s easy to restore the binary tree. The final result is shown below:

Second, the implementation

The implementation code

The implementation code is consistent with the idea. In order to avoid repeatedly looking for the target value in the middle order traversal, Map is used to store all the node values and positions in the middle order traversal.

    private Map<Integer, Integer> inMap;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = inorder.length;
        int m = postorder.length;
        // Construct a hash map, remembering the position of each node in the sequence traversal
        inMap = new HashMap<>();
        for (int i=0; i<n; i++) {
            inMap.put(inorder[i], i);
        }
        return dfs(postorder, 0, n-1, m-1);
    }

    / * * *@paramPostorder post-order traversal *@paramIn inLeft, order traverses the start bit * of the left subtree@paramInRight in order to traverse the start bit * of the right subtree@paramPostRoot Position of the root node in subsequent traversals *@return* /
    public TreeNode dfs(int[] postorder, int inLeft, int inRight, int postRoot) {
        if (inLeft > inRight)
            return null;
        // All nodes are root nodes from back to front
        TreeNode root = new TreeNode(postorder[postRoot]);
        int inorder_root = inMap.get(postorder[postRoot]);
        root.left = dfs(postorder, inLeft, inorder_root-1, postRoot-(inRight-inorder_root)-1);
        root.right = dfs(postorder, inorder_root+1, inRight, postRoot-1);
        return root;
    }
Copy the code

The test code

    public static void main(String[] args) {
        int[] inorder = {9.3.15.20.7};
        int[] postorder = {9.15.7.20.3};
        TreeNode treeNode = new Number106().buildTree(inorder, postorder);
        System.out.println("test");
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section