The nearest common ancestor of binary (search) tree ●●

236. The nearest common ancestor of a binary tree ●●

describe

Given a binary tree , Find two specified nodes in the tree Recent public ancestor .

The most recent definition of public ancestor is ：“ For a tree T Two nodes of p、q, The nearest common ancestor is represented as a node x, Satisfy x yes p、q Our ancestors and x As deep as possible （ A node can also be its own ancestor ）.”

Example

Input ：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output ：5
explain ： node 5 And nodes 4 The most recent public ancestor of is the node 5 . Because by definition, the nearest common ancestor node can be the node itself .

Answer key

1. After the sequence traversal （ to flash back ）

The first thing you can easily think of ： If you find a node , It is found that there are nodes in the left subtree p, A node appears in the right subtree q, perhaps Nodes appear in the left subtree q, A node appears in the right subtree p, So the node is the node p and q The latest public ancestor of .

But there is a second situation , Is the node itself p(q), It has a grandchild node q§.

Use post order traversal , The process of backtracking , Namely Traverse nodes from low to high , Once the node satisfying the first condition is found , This is the nearest public node .

But if p perhaps q Itself is the nearest public ancestor ？

Actually Just find a node that is p perhaps q When , Return the current node directly , There is no need to continue recursive subtrees . If the next （ Up ） The following node is found in the traversal （ Parent node ） If the first condition is met, the return value is modified to the subsequent node , otherwise , Continue to return to the found node .

When a recursive function has a return value ：
If you want to Search for an edge , When the return value of recursive function is not empty , Go back to ;

if ( Recursive function (root->left)) return ;
if ( Recursive function (root->right)) return ;

If you want to Search the whole tree , Just use a variable left、right Catch the return value , This left、right There is also the need for logic processing in the post order , That is to say, the logic to deal with intermediate nodes in post order traversal （ It's also retrospective ）.

left =  Recursive function (root->left);
right =  Recursive function (root->right);
left And right Logical processing of ;

• Time complexity O(N) ： among N Is the number of binary tree nodes ; In the worst case , You need to recursively traverse all the nodes of the tree .
• Spatial complexity O(N) ： In the worst case , The depth of recursion reaches N , System use O(N) The size of the extra space .

class Solution {
    
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
        if(root == q || root == p || root == NULL) return root;     //  Judge the current node 
        TreeNode* left = lowestCommonAncestor(root->left, p, q);    //  Traverse left subtree 
        TreeNode* right = lowestCommonAncestor(root->right, p, q);  //  Traversal right subtree 
        if(left != NULL && right != NULL){
    
            return root;    //  Both left and right subtrees have return values , Then the current is the nearest common ancestor 
        }else if(left != NULL){
    
            return left;    //  Only the left subtree has a return value 
        }else if(right != NULL){
    
            return right;   //  Only the right subtree has a return value 
        }
        return NULL;
    }
};

235. The nearest common ancestor of a binary search tree ●

describe

Given a binary search tree , Find two specified nodes in the tree Recent public ancestor .

The most recent definition of public ancestor is ：“ For a tree T Two nodes of p、q, The nearest common ancestor is represented as a node x, Satisfy x yes p、q Our ancestors and x As deep as possible （ A node can also be its own ancestor ）.”

Example

p = 4, q = 7; Output : 6
p = 2, q = 4; Output : 2

Answer key

Different from ordinary binary tree , Binary search trees are ordered , as long as Traverse from top to bottom When ,cur The node is the value in [p, q] In interval It indicates that the node cur It's the recent public ancestor , And you don't need to traverse the whole tree , Find the result and return directly .

1. Sequence traversal queue iteration

The search direction is not adjusted according to the size of the node , Low efficiency .

class Solution {
    
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
        int Min = min(p->val, q->val);
        int Max = max(p->val, q->val);
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
    
            TreeNode* curr = que.front();
            que.pop();
            if(curr->val <= Max && curr->val >= Min) return curr;
            if(curr->left) que.push(curr->left);
            if(curr->right) que.push(curr->right);
        }
        return NULL;
    }
};

2. The former sequence traversal

Judge and adjust the search direction according to the size of the node .

When the node value is greater than p、q When the value of , Search to the left subtree ;
When the node value is less than p、q When the value of , Search the right subtree ;
Otherwise, the node value is in the interval , Meet the conditions , Go straight back to .

recursive

class Solution {
    
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
        if(root == NULL) return NULL;

        if(root->val > p->val && root->val > q->val){
                       //  in 
            TreeNode* left = lowestCommonAncestor(root->left, p, q);    //  Left 
            if(left != NULL) return left;
        }

        if(root->val < p->val && root->val < q->val){
    
            TreeNode* right = lowestCommonAncestor(root->right, p, q);  //  Right 
            if(right != NULL) return right;
        }

        return root;	//  Node value is within the range 
    }
};

iteration

class Solution {
    
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
        while(root != NULL){
    
            if(root->val > p->val && root->val > q->val){
    
                root = root->left;	//  To the left 
            }else if(root->val < p->val && root->val < q->val){
    
                root = root->right;	//  To the right 
            }else return root;		//  Node value is within the range 
        }
        return NULL;
    }
};