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

preface

In question 105, the binary tree is constructed by traversing the sequence of preorder and middle order as follows:

Preorder and inorder of a tree are given. Construct a binary tree and return its root node.

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null, 15,7]Copy the code

A, thinking

Restore the binary tree by pre-order traversal and middle-order traversal

One caveat: neither preorder nor inorder has repeating elements

We can actually think about the question, why doesn’t a forward traversal restore a binary tree?

As an example, suppose the result of a pre-ordered traversal is [1, 2, 3]. Can you restore the binary tree? Obviously not, because there are two things that can happen.

The first case:

The second case:

But if you are told that the result of the preceding traversal is [1, 2, 3] and the result of the middle traversal is [2, 1, 3]. So it’s easy to see that this is the first case.

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

  • Foreorder traversal: root left and right
  • Middle order traversal: left root right

And because there is no repeated node value in the binary tree, the first node in the preceding traversal is the root node. So in a middle-order traversal, the value before the root node is the left subtree, and the value to the right is the right subtree. So we can restore the binary tree.

Graphic algorithm

In example 1, preorder = [3,9,20,15,7] and inorder = [9,3,15,20,7] are used as examples.

  1. Because of the nature of the pre-traversal, it is easy to know the first node3Is the root node

  1. The result of middle order traversal is divided into left subtree and right subtree according to root node

  1. Because the left subtree only has one node9, directly as a leaf node.We know that the left subtree has only one node, so the root node of the right subtree is the third node of the preceding traversal.

  1. The right subtree can be divided into left and right subtrees, as shown in the following figure:

  1. The final result is as follows:

Second, the implementation

The implementation code

The implementation code is basically consistent with the idea, the only thing that needs to be noted is that we first use HashMap to store the position of each node in the sequential traversal, so as to prevent the repeated search for the target position in the sequential traversal

    private Map<Integer, Integer> inMap;

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

    / * * * *@paramLeft The starting position of the left subtree * in the middle order traversal@paramStart position * in right subtree traversal@paramRootIndex Indicates the value of the root node *@return* /
    public TreeNode dfs(int[] preorder, int left, int right, int rootIndex) {
        if (left > right) {
            return null;
        }
        int inorder_root = inMap.get(preorder[rootIndex]);
        TreeNode root = new TreeNode(preorder[rootIndex]);
        root.left = dfs(preorder, left, inorder_root-1, rootIndex+1);
        root.right = dfs(preorder, inorder_root+1, right, rootIndex+inorder_root-left+1);
        return root;
    }
Copy the code

The test code

    public static void main(String[] args) {
        int[] preorder = {3.9.20.15.7};
        int[] inorder = {9.3.15.20 ,7};
        TreeNode treeNode  = new Number105().buildTree(preorder, inorder);
        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