Sword finger offer question brushing record - offer 07 Rebuild binary tree

Enter the results of preorder traversal and inorder traversal of a binary tree , Build the binary tree and return its root node .

It is assumed that the results of the input preorder traversal and the middle order traversal do not contain repeated numbers .

The preorder traversal order of binary tree is ：

Let's go through the root node ;

Then recursively traverse the left subtree ;

Finally, recursively traverse the right subtree .

The order of traversal in binary tree is ：

First recursively traverse the left subtree ;

Then traverse the root node ;

Finally, recursively traverse the right subtree .

stay 「 recursive 」 In the process of traversing a subtree , We also regard this subtree as a brand new tree , Traverse in the above order . mining 「 The former sequence traversal 」 and 「 In the sequence traversal 」 The nature of , We can get the solution of this problem .

Ideas

For any tree , The form of preorder traversal is always
[ The root node , [ The result of preorder traversal of left subtree ], [ The result of preorder traversal of the right subtree ] ]
That is, the root node is always the first node in the preorder traversal . And the form of middle order traversal is always
[ [ Middle order traversal results of left subtree ], The root node , [ The middle order traversal result of the right subtree ] ]
As long as we locate the root node in the middle order traversal , Then we can know the number of nodes in the left subtree and the right subtree respectively . Because the length of preorder traversal and medial traversal of the same subtree is obviously the same , So we can correspond to the result of preorder traversal , Position all left and right brackets in the above form .

Since then , We know the results of preorder traversal and medial traversal of left subtree , And the results of preorder traversal and medial traversal of the right subtree , We can construct left subtree and right subtree recursively , Then connect the two subtrees to the left and right positions of the root node .

details

When the root node is located in the middle order traversal , A simple method is to scan the whole result of the middle order traversal directly and find the root node , But it's time-consuming . We can consider using a hash table to help us quickly locate the root node . For each key value pair in the hash map , A key represents an element （ The value of the node ）, Value indicates where it appears in the middle order traversal . Before the process of constructing a binary tree , We can scan the list of traversal in the middle order again , You can construct this hash map . In the process of constructing the binary tree , We just need O(1)O(1) Time to locate the root node .

The following code gives detailed comments .

class Solution {
    private Map<Integer, Integer> indexMap;

    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return null;
        }

        //  The first node in preorder traversal is the root node 
        int preorder_root = preorder_left;
        //  Locate the root node in the middle order traversal 
        int inorder_root = indexMap.get(preorder[preorder_root]);
        
        //  First set up the root node 
        TreeNode root = new TreeNode(preorder[preorder_root]);
        //  Get the number of nodes in the left subtree 
        int size_left_subtree = inorder_root - inorder_left;
        //  The left subtree is constructed recursively , And connect to the root node 
        //  In the first order traversal 「 from   Left boundary +1  At the beginning  size_left_subtree」 Elements correspond to the middle order traversal 「 from   Left boundary   Start to   Root node localization -1」 The elements of 
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        //  Construct the right subtree recursively , And connect to the root node 
        //  In the first order traversal 「 from   Left boundary +1+ The number of nodes in the left subtree   Start to   Right border 」 The element corresponding to the middle order traversal 「 from   Root node localization +1  To   Right border 」 The elements of 
        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        //  Construct a hash map , Help us quickly locate the root node 
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
}