Brush questions of binary tree (5)

One 、 The nearest common ancestor of a binary search tree

• For a tree T, Connected nodes of ,p1,p2, Its common ancestor is x, And x The depth should be as large as possible
• A node can also be its own ancestor
• All node values of binary search tree are unique , You can directly compare through the node value

Solution 1 : Second traversal ( recommend )

• Using the properties of binary search number , Find the target from the root node , If the current node is smaller than the target, enter the right subtree , If you are big, go into the left subtree , Until we find the target node , Use an array to record the elements encountered
• And then find them in the binary search tree p1,p2 These two nodes , And record their paths with an array
• Traversing two arrays at the same time , Compare node values , The last equivalent element is the nearest common ancestor

class Solution {
    
public:
    /** *  The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly  * * * @param root TreeNode class  * @param p int integer  * @param q int integer  * @return int integer  */
    vector<int>getPath(TreeNode*root,int target)
    {
    
        vector<int>v;
        TreeNode*node=root;
        while(node->val!=target)
        {
    
            v.push_back(node->val);
            if(target<node->val)// The small one is on the left 
                node=node->left;
            else// The big one is on the right 
                node=node->right;
        }
        v.push_back(node->val);
        return v;
    }
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
    
        // write code here
        vector<int>p1=getPath(root, p),p2=getPath(root,q);
        int target;
        // Compare two paths , Find the first difference 
        for(int i=0;i<min(p1.size(),p2.size());i++)
        {
    
            if(p1[i]==p2[i])
                target=p1[i];// The last same node is the common value 
            else
                break;
        }
        return target;
    }
};

Time complexity :O(n), The worst , A binary tree degenerates into a linked list , Finding the target requires O(n), The same as the first half of the comparison path also needs O(n)
Spatial complexity :O(n), The longest record path array is n

Solution 2 : One traverse

if p,q Are less than or equal to this node value , be p,q All in the left subtree of this node , On the contrary, right subtree , If one is big and the other is small , Then this node is the common ancestor , Only recent public ancestors will p,q Put in different subtrees , Use recursion to solve

• Priority judgment is empty
• For a certain node , And p,q Compare the size , Judging from the above description
• if p,q Are on the left side of this node , Recursion into the left subtree ,
• On the contrary, enter the right subtree

class Solution {
    
public:
    /** *  The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly  * * * @param root TreeNode class  * @param p int integer  * @param q int integer  * @return int integer  */
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
    
        // write code here
        if(root==NULL)
            return -1;
        if((p>=root->val&&q<=root->val)||(p<=root->val&&q>=root->val))// Different common ancestors on both sides 
            return root->val;
        else if(p<=root->val&&q<=root->val)
            return lowestCommonAncestor(root->left, p, q);// Less than left recursion 
        else
            return lowestCommonAncestor(root->right,  p, q);// Greater than right 
    }
};

Time complexity :O(n), At worst, traverse all nodes of the binary tree
Spatial complexity :O(n), The worst recursion stack depth is n

Two 、 Find the nearest common ancestor of two nodes in the binary tree

The problem ensures that the node values of the binary tree are different

Solution 1 : Path comparison ( recommend )

• utilize dfs Find the path from the root node to the two target nodes , Each time you select a subtree of a binary tree, look down , At the same time, the array of storage paths increases the node value of traversal , When the leaf node does not exist , Back to the parent node , Find another path , When backtracking, remove the newly added elements in the array
• Traverse the array of two paths , Compare element values
• The last same node of the two paths is the nearest common ancestor

class Solution {
    
public:
    /** * * @param root TreeNode class  * @param o1 int integer  * @param o2 int integer  * @return int integer  */
    bool flag =false;// Record whether the path is found 
    void dfs(TreeNode*root,vector<int>&path,int target)
    {
    
        if(flag||root==NULL)
            return ;
        path.push_back(root->val);
        if(root->val==target)
        {
    
            flag=true;
            return ;
        }
        dfs(root->left,path,target);//dfs Traversal search 
        dfs(root->right,path,target);
        if(flag)
            return ;
        path.pop_back();// The path has not been found , Then the subtree does not , to flash back 
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
    
        // write code here
        vector<int>v1,v2;
        dfs(root,v1,o1);
        flag=false;//flag As a global variable, you need to reset 
        dfs(root,v2,o2);
        int result;
        for(int i=0;i<min(v1.size(),v2.size());i++)
        {
    
            if(v1[i]==v2[i])
                result=v1[i];
            else
                break;
        }
        return result;
    }
};

Time complexity :O(n),n For the node number , First recursively traverse the node to find the path , After traversing the path to find ancestors
Spatial complexity :O(n), The worst binary tree degenerates into a linked list , The recursive stack depth and path array size are n

Solution 2 : recursive

• If either of the two nodes matches the root node , be root For the nearest public ancestor
• If they don't match , Recursive left subtree respectively , Right subtree
• If a node is in the left subtree , A node is in the right subtree , Then the root node is the target node
• If both are in the left subtree , Then recursion to the left , On the contrary, to the right

class Solution {
    
public:
    /** * * @param root TreeNode class  * @param o1 int integer  * @param o2 int integer  * @return int integer  */
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
    
        // write code here
        if(root==NULL)
            return -1;
        if(root->val==o1||root->val==o2)// Match return 
            return root->val;
        int left=lowestCommonAncestor(root->left, o1, o2),
        right=lowestCommonAncestor(root->right, o1, o2);
        if(left==-1)// It's not on the left, it's on the right 
            return right;
        if(right==-1)
            return left;
        return root->val;// otherwise · The root is the current node 
    }
};

Time complexity :O(n),n For the node number , Recursively traversing nodes
Spatial complexity :O(n), The worst binary tree degenerates into a linked list , The recursive stack depth is n

3、 ... and 、 Serialize binary tree

Traversing the binary tree , Record nodes , When traversing in the same way, you can restore the binary tree , Its storage is the serialization of binary tree
There are four traversal methods : front 、 in 、 after 、 Sequence traversal

Solution 1 : The former sequence traversal ( recommend )

• Prioritize serialization , Use the serialization function to traverse in sequence , When encountering an empty node, add #, Non empty add node value and ’|' As a divider , Then enter the left , Right subtree recursion
• Use the reverse serialization function to recursively construct the subtree first , encounter ’#' Empty node , Encounter numbers according to ‘|’ Division , Convert the string into a number and add it to the creation node , Then create left subtrees respectively , Right subtree .

class Solution {
    
public:
    void SerializeFunctiion(TreeNode*root,string&str)
    {
    
        if(root==NULL)
        {
    
            str+='#';
            return ;
        }
        string tmp=to_string(root->val);// Built in functions that convert numbers to characters 
        str+=tmp+'|';
        SerializeFunctiion(root->left, str);// Recursively serialize the left and right subtrees 
        SerializeFunctiion(root->right, str);
    }
    char* Serialize(TreeNode *root) {
        
        if(root==NULL)
            return "#";
        string tmp;
        SerializeFunctiion(root, tmp);
        char*transchar=new char[tmp.length()+1];// take string Turn into char
        strcpy(transchar,tmp.c_str());
        transchar[tmp.length()]='\0';
        return transchar;
    }
    TreeNode*DeserializeFunction(char**str)
    {
    
        // When reaching the leaf node , Creation completed , Go back and continue to create the parent node 
        if(**str=='#')
        {
    
            (*str)++;
            return NULL;
        }
        // Converts characters to Numbers 
        int val=0;
        while(**str!='|'&&**str!='|')
        {
    
            val=val*10+((**str)-'0');
            (*str)++;
        }
        TreeNode*root=new TreeNode(val);
        if(**str=='\0')// After the creation , Return results 
            return root;
        else
            (*str)++;
        root->left=DeserializeFunction(str);// The left and right subtrees are deserialized respectively 
        root->right=DeserializeFunction(str);
        return root;
    }
    TreeNode* Deserialize(char *str) {
    
        if(*str=='#')
            return NULL;
        TreeNode*node=DeserializeFunction(&str);
        return node;
    }
};

Time complexity :O(n), Go through the nodes first
Spatial complexity :O(n), Maximum depth of recursive stack

Solution 2 : Sequence traversal

class Solution {
    
public:
    char* Serialize(TreeNode *root) {
        
        string ret;
        if(!root) 
            return NULL;
        queue<TreeNode*> q;
        q.emplace(root);    //  The root node joins the queue 
        ret += to_string(root->val) + '|';    //  Record node value 
        while(!q.empty()){
    
            TreeNode* p = q.front(); 
            q.pop();   
            if(p->left){
        //  If not be empty , add "val" + "!"
                ret += to_string(p->left->val) + '|';
                q.emplace(p->left);
            }
            else ret += '#';    //  Empty plus '#'

            if(p->right){
    
                ret += to_string(p->right->val) + '|';
                q.emplace(p->right);
            }
            else ret += '#';
        }
        char* transchar = new char[ret.size() + 1];
        strcpy(transchar, ret.c_str());
        return transchar;
    }

    TreeNode* Deserialize(char *str) {
    
        if(!str) 
            return NULL;
        string data = string(str);
        vector<string> v;     //  First pair data Prepare for it 

        for(int i = 0; i < data.size(); i++){
    
            if(data[i] == '#') 
                v.push_back(string("#"));    //  If it is empty, use "#" Express 
            else{
    
                int j = i;
                while(data[j] != '|') 
                j++;
                v.push_back(data.substr(i, j - i));    //  If it is not empty, use "val" Express 
                i = j;
            }
        }
        // stoi() The function can change string Convert to int
        TreeNode* root = new TreeNode(stoi(v[0]));    //  Create a root node 
        queue<TreeNode*> q;
        q.emplace(root);    //  Root in line 
        int k = 1;
        while(k < v.size()){
    
            TreeNode* p = q.front(); 
            q.pop();
            TreeNode *left=NULL,*right=NULL;
            if(v[k] != "#"){
        //  If the left son is not empty 
                left = new TreeNode(stoi(v[k]));
                q.emplace(left);
            }
            p->left = left;
            if(v[k + 1] != "#"){
        //  If the right son is not empty 
                right= new TreeNode(stoi(v[k + 1]));
                q.emplace(right);
            }
            p->right = right;
            k += 2;    //  The pointer moves back two steps 
        }

        return root;
    }
};

Construct binary tree in a non recursive way
Time complexity ：O(n), n For the node number , The time complexity of sequence traversal is O(n)
Spatial complexity ：O(n), Serialization uses a queue , Deserialization uses a vector, The time complexity is O(n)