Jianzhi offer 07 rebuild binary tree -- construct binary tree from middle order and post order traversal sequence

The finger of the sword Offer 07. Reconstruction of binary tree

The finger of the sword Offer 07. Reconstruction of 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 .

Example 1:

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

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

Thought analysis

First of all, you need to know what characteristics the traversed array has

• In the preorder traversal sequence , The first element is the root node of the tree
• In the middle order traversal sequence , The left side of the root node is the left subtree , The right side of the root node is the right subtree

According to the above theoretical knowledge, we can know the problem-solving strategy of this problem , That is to say The first element of the preamble array 【 The root node 】 Is the cutting point , Cut the array in the middle first , According to the middle order array , In turn, order the array before cutting . Cut one layer at a time , The first element of each pre ordered array is the node element .

The first element of the preorder traversal is its head node . Got the head node , We can find the position of the head node in the middle order traversal index. adopt index We can find the length of the left subtree in the array ： index - inorder_start.（inorder_start It is the starting point of middle order traversal ）.

1. Get the head node of the tree int root_val = preorder[preorder_start] (preorder_start Is the starting value of preorder traversal ). Then we build the binary tree directly The root node TreeNode* root = new TreeNode(root_val)

2. Build the left tree ：root->left We know that the length of the left subtree of the binary tree is left_length = index - inorder_start

   So we can deduce that the position of the left subtree of the binary tree in the preorder traversal is [preorder_start+1,preorder_start+left_length].
   Empathy ： The position of the left subtree of the binary tree in the middle order traversal is [inorder_start, index - 1].

3. Build the right tree ：root->right
   The position of the right subtree of the binary tree in the preorder traversal is [preorder_start+left_length+1,preorder_end].
   Empathy ： The position of the right subtree of the binary tree in the middle order traversal is [index + 1 , inorder_end].
   The code is as follows ：

class Solution {
    
public:
    // Recursive code 
    TreeNode* buildcore(const vector<int>& preorder, const vector<int>& inorder, int preorder_start, int preorder_end, int inorder_start, int inorder_end)
    {
    
        if(preorder_start>preorder_end||inorder_start>inorder_end)
        {
    
            return nullptr;
        }
        // The first number of preorder traversal is the value of the root node 
        int root_val = preorder[preorder_start];
        TreeNode* root = new TreeNode(root_val);
        // There is only one value in the interval , return 
        if(preorder_start == preorder_end)
        {
    
            return root;
        }
        // Middle order traversal finds the location of the root node 
        int index = 0;
        // Can be equal to , In scope 
        while(index <= inorder_end && inorder[index] != root_val)
        {
    
            index++;
        }
        // If index Greater than inorder_end, It means that we didn't find , Report errors , The meaning of the title is that you can definitely find , So there is no judgment here .
        // The interval size of left and right subtrees .
        int left_length = index - inorder_start;

        root->left = buildcore(preorder,inorder,preorder_start+1,preorder_start+left_length,inorder_start,index-1);
        root->right = buildcore(preorder,inorder,preorder_start+left_length+1,preorder_end,index+1,inorder_end);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
    
        int n = preorder.size();
        if(n==0)
        {
    
            return 0;
        }
        return buildcore(preorder,inorder,0,n-1,0,n-1);
    }
};

106. Construct binary tree from middle order and post order traversal sequence

106. Construct binary tree from middle order and post order traversal sequence

This question is similar to the previous one , The same solution can be used to solve recursively .

Thought analysis

• In a postorder traversal sequence , The last element is the root node of the tree

• In the middle order traversal sequence , The left side of the root node is the left subtree , The right side of the root node is the right subtree

With The last element of the sequenced array 【 The root node 】 Is the cutting point , Cut the array in the middle first , According to the middle order array , Conversely, after cutting the array . Cut one layer at a time , The last element of each subsequent array is the node element .

class Solution {
    
public:
    TreeNode* buildcore(const vector<int>& inorder, const vector<int>& postorder, int inorder_start, int inorder_end, int post_start, int post_end)
    {
    
        if(inorder_start>inorder_end||post_start>post_end)
        {
    
            return nullptr;
        }
        // The last value of post order traversal is the root node 
        int root_val = postorder[post_end];
        TreeNode* root = new TreeNode(root_val);
        // Traverse to find the position of the root node in the middle order 
        int index = 0;
        for(index = 0; index<= inorder_end; index++)
        {
    
            if(inorder[index] == root_val)
            {
    
                break;
            }
        }
        // Calculate the length of the left subtree 
        int left_length = index - inorder_start;
        // Build the left subtree 
        root->left = buildcore(inorder,postorder,inorder_start,index-1,post_start,post_start+left_length-1);
        // Build the right subtree 
        root->right = buildcore(inorder,postorder,index+1,inorder_end,post_start+left_length,post_end-1);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 
    {
    
        int n = inorder.size();
        if(n==0)
        {
    
            return nullptr;
        }
        return buildcore(inorder,postorder,0,n-1,0,n-1);
    }
};