236. The nearest common ancestor of a binary tree

236. The nearest common ancestor of a binary tree

Given a binary tree , Find the nearest common ancestor of the two specified nodes in the tree .

Baidu Encyclopedia The definition of the most recent common ancestor in 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 1：

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

Example 2：

 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 .

Example 3：

 Input ：root = [1,2], p = 1, q = 2
 Output ：1

Tips ：

• The number of nodes in the tree is in the range [2, 105] Inside .
• -109 <= Node.val <= 109
• all Node.val Different from each other .
• p != q
• p and q All exist in a given binary tree .

Ideas :

function lowestCommonAncestor The return value of is node p and q The latest public ancestor of , It's easy to think of , From bottom to top , Check each node in turn , Is it a node p and q The latest public ancestor of .

Need to meet the conditions :

• p and q stay root On both sides of
• perhaps q perhaps p be equal to root, Another node is root In the subtree

Deep understanding of functions lowestCommonAncestor The return value of :

• If not in the tree p And there's no q, Just go back to NULL
• If there is only p Or just q, Just go back to p perhaps q
• Yes p And there are q, Return to the nearest common ancestor

Arrangement :

Combined with the above ideas , You can think of , Using recursion , Until I find p and q, Then in the recursive backtracking process , Solve the problem . Refer to the idea of code Capriccio :

• Determine the return value and parameters of the recursive function

​ The meaning of the return value is : node p and q The latest public ancestor of

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)

• Determine termination conditions

  • If not in the tree p And there's no q, Just go back to NULL

  • If there is only p Or just q, Just go back to p perhaps q

            if (!root) return NULL;
            if (root == q || root == p) return root;
    

• Recursive logic
  • If left and right All have non empty return values , explain root It's the latest public ancestor
  • If one is empty , Then the non empty one is root For the tree of the root node lowestCommonAncestor Function return value
  • If it's all empty , be NULL In order to root For the tree of the root node lowestCommonAncestor Function return value

        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);		

Code :

class Solution {
    
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
        if (!root) return NULL;
        if (root == q || root == p) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left && right) 
            return root;
        else if (!left) 
            return right;
        else 
            return left;

    }
};

summary :

Although this is a simple question , But I understand for a long time , Write an explanation and take notes .