Detailed explanation of leetcode reconstruction binary tree [easy to understand]

Hello everyone , I meet you again , I'm your friend, Quan Jun .

LeetCode Detailed explanation of reconstructing binary tree

• Title Description
• Principle analysis
  • （1） General train of thought
  • （2） Detailed description
• Code implementation
  • （1） The main function
  • （2） Recursive function
    • Determination of parameter interval
    • The condition for the end of recursion
• summary

Title Description

Principle analysis

（1） General train of thought

So let's talk about that , The former sequence traversal + How to determine a unique binary tree by middle order traversal . Basic knowledge about binary tree , Please have a look at Basic operation and connection of binary tree . This will not be repeated too much . For the preorder traversal order ： root 、 The left subtree 、 Right subtree ; For the traversal order of the middle order ： The left subtree 、 root 、 Right subtree . So through preorder traversal , The first node we get in the preamble is the root of the tree , Then find the position of the node in the middle order traversal . In the middle order , All the nodes on the left side of the root belong to the left subtree of the root , The right side of the root is full of nodes belonging to the right subtree of the root . Details are shown in the picture ：

After the first step , We will find that , At present, we only specifically determine which is the root node , Which nodes belong to the left and right subtrees . But because of the tree Recursive property . The nodes belonging to the left subtree still conform to the preorder traversal , The characteristics of medium order traversal . So we just need to use the above method again for the two parts just separated , Determine the root node , Determine which nodes belong to the left subtree , Which nodes belong to the right subtree . One analogy , Until the end . This is the general idea of this problem .

（2） Detailed description

There are still many places worth thinking about this problem . 1、 How can we express which nodes belong to the left subtree , Right subtree ？ answer ： Before the order 、 The middle order is given vector, So we can determine the range by subscript . Before the order ：【 root , The left subtree , Right subtree 】. Middle preface ：【 The left subtree , root , Right subtree 】. They are all three categories, and the nodes are all concentrated , Good distinction . 2、 What is the end condition of recursion ？ answer ： This still needs to be combined with specific code analysis , What is certain at present is , When we control the scope , If the scope is illegal （ non-existent ） The situation shows that there is no left subtree or right subtree , We're going back to .

Code implementation

notes ： Usually in my solution , Range control , The reason why the code is written in this way will be written next to the corresponding code through comments , Help readers understand the analysis code , This is more targeted . therefore , If the reader has doubts or does not understand the previous topic analysis , Please read the code and the notes carefully , It will inspire you , Help you understand ！！

（1） The main function

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { 
   
	//_buildTree This problem requires recursive implementation , So we need to use a recursive function .
       return _buildTree(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
    }

Copy

Here I want to explain in detail the parameters and functions of this recursive function The first parameter ： It's the preorder traversal vector, There's not much to explain The second parameter ：preStart, It is at the beginning of the preorder of the subproblem . Say in detail , After we determine the root , We will recurse the left and right subtrees , The starting position of the left and right subtrees should be determined . The third parameter ：preEnd： It is at the end of the preorder of the subproblem , This guarantees preStart And preEnd Between them is the node sequence of the subproblem . Fourth parameter It is traversal in middle order vector Fifth parameter ：inStart, Is the starting position of the order traversal in the subproblem Sixth parameter ：inEnd, Is the end position of the sequence traversal in the sub problem

（2） Recursive function

	TreeNode* _buildTree(vector<int>& preorder,int preStart,int preEnd,vector<int>&inorder,int inStart,int inEnd)
    { 
   
        if(preStart>preEnd)
        { 
   
            return nullptr;
        }
        // We can directly determine the root node , So we first create the root node 
        TreeNode* root = new TreeNode(preorder[preStart]);
        // After finding the root node , We take the value of the root node and find the corresponding position in the middle order traversal , Distinguish left and right subtrees 
        for(int i=inStart;i<=inEnd;i++)
        { 
   
        	// Find the middle order traversal position of the root node 
            if(inorder[i] == preorder[preStart])
            { 
   
            	// Because the recursive function completes the construction of the sub problem tree , All that make a big problem root The left and right subtrees can be linked separately 
                root->left = _buildTree(preorder,preStart+1,preStart+i-inStart,inorder,inStart,i-1);
                root->right = _buildTree(preorder,preStart+i-inStart+1,preEnd,inorder,i+1,inEnd);
            }
        }
        return root;
    }

Copy

Determination of parameter interval

The key is how many parameters are passed in the recursive subproblem .

size:size Is the number of nodes in the left subtree, so size = i-inStart therefore ：root->left = _buildTree(preorder,preStart+1,preStart+i-inStart,inorder,inStart,i-1); xxxxxxroot->right = _buildTree(preorder,preStart+i-inStart+1,preEnd,inorder,i+1,inEnd); Readers can understand by comparing themselves

The condition for the end of recursion

The next step is to determine how to end recursion , Is the first recursive function if. We mentioned that before , If the interval of the subtree of the subproblem does not exist, the cycle can be ended , So how can it be called nonexistence ？ We have just obtained the range of the preorder of each subtree 【preStart,preEnd】, If preStart==preEnd When , It means that the subtree also has a node , Still need to cycle , But is it possible preStart>preEnd Well ？ The answer is yes . When we find the recursive subproblem preStart = preStart+1,preStart Growing , And recursive subproblem preEnd = preStart+size-1. The analysis and comparison are ： When the subtree has only one node （size == 1） yes ,preStart == preEnd. After recursion again ,size == 0, therefore preStart > preEnd. It means there is no subtree , Can return nullptr 了 . So get the code ：if (preStart>preEnd) return nullptr;

summary

xxxx See the binary tree problem , What our prime minister should think of is function recursion , Therefore, binary tree has good “ Recursive property ”, Every subtree is a binary tree , All meet the characteristics of trees , If the subproblem has the same characteristics, recursive algorithm can be used . Secondly, we should know clearly , Binary tree “ front 、 in 、 after , Sequence traversal ”, And know the relationship and differences between them . After having the above thoughts and reserve knowledge , We can write code logic with certain ideas . Another important part of this problem is the preface of the control subproblem 、 Middle preface vector Scope limit of . Truly ensure the unity of the subproblem and the original problem xxxx This is the complete analysis of this problem , If you have a better idea , Or where I can optimize my code , Please point out , I will study with an open mind . I hope we can study together , Progress together ！！

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/131500.html Link to the original text ：https://javaforall.cn