One 、 Reconstruction of binary tree

Using the results of preorder and inorder traversal to reconstruct the binary tree

Solution 1 : recursive ( recommend )

• First, create the root node from the first point traversed by the previous sequence ‘
• Traverse the middle order traversal results to find the position of the root node in the array
• Divide the two traversal arrays into sub arrays according to the number of sub tree nodes , The subarray recursively constructs the root node of the subtree , Repeat the above operation
• Until the length of the subtree sequence is 0, End recursion

class Solution {
    
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
    
        int n=pre.size(),m=vin.size();
        if(n==0||m==0)
            return NULL;
        TreeNode*root=new TreeNode(pre[0]);// Build the root node 
        for(int i=0;i<vin.size();i++)
        {
    
            if(pre[0]==vin[i])// Find the first element of the preorder traversal in the preorder traversal , Split sequence 
            {
    
                vector<int>leftpre(pre.begin()+1,pre.begin()+i+1);// Left subtree preorder traversal 
                vector<int>leftvin(vin.begin(),vin.begin()+i);// Left subtree middle order traversal 
                vector<int>rightpre(pre.begin()+i+1,pre.end());// Right subtree preorder traversal 
                vector<int>rightvin(vin.begin()+i+1,vin.end());// Order traversal in right subtree 
                root->left=reConstructBinaryTree(leftpre, leftvin);// Build the left subtree 
                root->right=reConstructBinaryTree(rightpre, rightvin);// Build the right subtree 
            }
        }
        return root;
    }
};

Time complexity :O(n), Recursively build nodes n Time
Spatial complexity :O(n), The maximum depth of recursive stack does not exceed n, The length of auxiliary array does not exceed n

Solution 2 : Stack

• First, the first node of the preorder traversal is the root node , Establish auxiliary stack
• There are only two cases for two adjacent numbers in preorder traversal , One is , The latter is the left node of the former , The other is that the latter is the right node of the former or its ancestor , Judge according to this
• Traverse two sequences at the same time , Judge whether the segment is a left node , If so, continue to judge to the left , Record ancestors with stack , If it is not , Go back to the corresponding ancestor , Enter the right subtree to judge
  

class Solution {
    
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
    
        int n=pre.size(),m=vin.size();
        if(n==0||m==0)
            return NULL;
        stack<TreeNode*>s;
        TreeNode*root=new TreeNode(pre[0]);// Establish root node 
        TreeNode*cur=root;
        for(int i=1,j=0;i<n;i++)
        {
    
            if(cur->val!=vin[j])// Next to this is his left node 
            {
    
                cur->left=new TreeNode(pre[i]);
                s.push(cur);
                cur=cur->left;
            }
            else// Otherwise, it is his right node or ancestor right node 
            {
    
                j++;
                while(!s.empty()&&s.top()->val==vin[j])// Pop up to the matching ancestor 
                {
    
                    cur=s.top();
                    s.pop();
                    j++;
                }
                cur->right=new TreeNode(pre[i]);
                cur=cur->right;
            }
        }
        return root;
    }
};

Time complexity :O(n) Traverse the array once , Pop up stack at most n Time
Spatial complexity :O(n), The maximum stack space is n

Two 、 Output the right view of the binary tree

Solution 1 : Recursive tree building +dfs( recommend )

• Check the size of the two traversal sequences , if 0, return NULL
• Build up trees , The first element is the root node every time the preorder is traversed , Find the node in the middle order traversal and divide the left and right subtrees , Split array recursive tree
• dfs When printing the right view, use a hash table to store the rightmost node corresponding to each depth , Initialize two stack auxiliary traversals , A record dfs Node at , Another record depth , The root node is put on the stack first
• For each access node , Left child node advanced stack , Right child node backward , By the nature of stack , When coming out of the stack, the right side is accessed first ,
• When there are no elements in this layer of the hash table , The first node encountered by this layer is the rightmost node
• Use a variable to maintain the maximum depth layer by layer , Finally, traverse the depth , Read the rightmost node of each depth from the hash table and add it to the array

class Solution {
    
public:
    // four int Class data respectively represents the leftmost subscript of the preorder , Middle order leftmost subscript , The right most subscript of the first order , Middle order rightmost subscript 
    TreeNode*buildTree(vector<int>&pre,vector<int>&vin,int l1,int l2,int r1,int r2)
    {
    
        if(l1>r1||l2>r2)
            return NULL;
        TreeNode*root=new TreeNode(pre[l1]);
        int vin_root_index=0;// Save the subscript of the root node in the middle order traversal array 
        for(int i=l2;i<=r2;i++)
        {
    
            if(vin[i]==pre[l1])
            {
    
                vin_root_index=i;
                break;
            }
        }
        int leftsize=vin_root_index-l2,// Left subtree size 
        rightsize=r2-vin_root_index;// Right subtree size 
        // Recursively build subtrees 
        root->left=buildTree(pre, vin, l1+1,l2 ,l1+leftsize, l2+leftsize-1);
        root->right=buildTree(pre, vin, r1-rightsize+1, vin_root_index+1, r1, r2);
        return root;
    }
    vector<int>dfs(TreeNode*root)
    {
    
        unordered_map<int, int>m;// On the right is the deepest value 
        int max_depth=-1;// Record the maximum depth 
        stack<TreeNode*>nodes;// Maintain deep access nodes 
        stack<int>depths;// maintain dfs Depth at 
        nodes.push(root);
        depths.push(0);
        while(!nodes.empty())
        {
    
            TreeNode*node=nodes.top();
            nodes.pop();
            int depth=depths.top();
            depths.pop();
            if(node!=NULL)
            {
    
                max_depth=max(depth,max_depth);
                if(m.find(depth)==m.end())// Insert node when it does not exist 
                    m[depth]=node->val;
                nodes.push(node->left);
                nodes.push(node->right);
                depths.push(depth+1);
                depths.push(depth+1);
            }
        }
        vector<int>tmp;
        for(int i=0;i<=max_depth;i++)
            tmp.push_back(m[i]);
        return tmp;
    }
    vector<int> solve(vector<int>& pre, vector<int>& vin) {
    
        // write code here
        vector<int>tmp;
        if(pre.size()==0)
            return tmp;
        TreeNode*root=buildTree(pre,vin, 0, 0, pre.size()-1, vin.size()-1);
        // Each layer returns the rightmost node 
        return dfs(root);
    }
};

Time complexity :O(n^2), Tree building recursion O(n), Middle order traversal loop search O(n),dfsO(n), by O( n ^2)
Spatial complexity : Recursive stack , Hashtable , The space of the stack is O(n)

Solution 2 : Recursive tree building of hash table optimization + Sequence traversal

• Check the size of the traversal array
• Traverse the pre ordered array , Use the hash table to map the value in the middle order traversal with the subscript of the previous order traversal
• Divide the molecular tree recursively according to solution one , However, you can use the hash table to directly find the location of the root node in the medium order traversal array
• Establish queue auxiliary level traversal
• Use a variable to record the current queue size , When the value of the variable is 0 When you reach the rightmost , Record the node element

class Solution {
    
public:
    unordered_map<int,int>index;
    TreeNode*buildTree(vector<int>&pre,vector<int>&vin,int l1,int r1,int l2,int r2)
    {
    
        if(l1>r1||l2>r2)
            return NULL;
        int pre_root=l1;// The first node of the preorder traversal is the root node 
        int vin_root=index[pre[pre_root]];// Locate the root node in the middle order traversal 
        TreeNode*root=new TreeNode(pre[pre_root]);
        int leftsize=vin_root-l2;// Number of left subtree nodes 
        root->left=buildTree(pre, vin, l1+1, l1+leftsize, l2,vin_root-1);
        root->right=buildTree(pre, vin, l1+leftsize+1, r1, vin_root+1, r2);
        return root;
    }
    vector<int>dfs(TreeNode*root)
    {
    
        vector<int>v;
        queue<TreeNode*>q;
        q.push(root);
        while(!q.empty())
        {
    
            int size=q.size();// Record the number of nodes in this layer 
            while(size--)
            {
    
                TreeNode*tmp=q.front();
                q.pop();
                if(tmp->left)
                    q.push(tmp->left);
                if(tmp->right)
                    q.push(tmp->right);
                if(size==0)// Rightmost element 
                    v.push_back(tmp->val);
            }
        }
        return v;
    }
    vector<int> solve(vector<int>&pre, vector<int>&vin) {
    
        // write code here
        vector<int>tmp;
        if(pre.size()==0)
            return tmp;
        for(int i=0;i<pre.size();i++)
            index[vin[i]]=i;
        TreeNode*root=buildTree(pre, vin, 0, pre.size()-1, 0, vin.size()-1);
        return dfs(root);
    }

Time complexity :O(n), among n Is the number of binary tree nodes , Once per node , The hash table directly accesses the elements in the array
Spatial complexity :O(n), Recursive stack depth 、 Hashtable 、 The space of the queue is O(n)