【LeetCode 43】236. The nearest common ancestor of binary tree

【LeetCode 43】236. The nearest common ancestor of a binary tree

One 、 The question

Two 、 The answer process

** Ideas / Method ：** This question uses bottom-up search ------ to flash back ！ Recursion is also used ！

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 .

Use After the sequence traversal , Backtracking process , It is to traverse nodes from low to high , Once the node of this condition is found , It's the nearest public node .

• First find the node path p and q
• At the nearest common ancestor node of the node path

Logical processing in recursive trilogy ：

//
 //3. Traverse the whole tree 
        TreeNode *left=lowestCommonAncestor(root->left,p,q);
        TreeNode *right=lowestCommonAncestor(root->right,p,q);

When a recursive function has a return value ：

• Search for an edge ：

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

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

• Search the whole tree ：

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

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 you 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 ）

class Solution {
    
public://1.
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
       //2. If a node is found p Or nodes q Or an empty node is encountered . Just go back to 
        if(root==q||root==p||root==NULL) return root;
        //3. Traverse the whole tree 
        TreeNode *left=lowestCommonAncestor(root->left,p,q);// Constantly traverse the left subtree 
        TreeNode *right=lowestCommonAncestor(root->right,p,q);// Constantly traverse the right subtree 
        // Discussion ：
        if(left!=NULL&&right!=NULL) return root;

        if(left==NULL&&right!=NULL) return right; 
        else if(left!=NULL&&right==NULL) return left;
        else{
    //left==NULL&&right==NULL
            return NULL;
        }
    }
};