236. The nearest common ancestor of a binary tree (medium)

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 .

In Baidu Encyclopedia, 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 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 .

Ideas （dfs）

Think about what is a common ancestor node

• The left and right subtrees of this node each contain the target node
• The node itself is a target node , The subtree in one direction contains another target node

if ((left && right) || ((root->val == p->val || root->val == q->val) && (left || right))) {
    
            ancestor = root;
}

Then the above is the judgment condition , We use it bool Value to mark the situation of each child node

 bool left = dfs(root->left, p, q);//  Recursive left subtree , Judge its true value 
 bool right = dfs(root->right, p, q);//  Recursive right subtree , Judge its true value 

Recursion from bottom to top , Of the child nodes of the upper layer bool The value is determined by the node of the next layer

The picture comes from the official explanation
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/

Source code

class Solution {
    
public:
    TreeNode* ancestor;
    bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
    
        if (root == nullptr) {
    
            return false;
        }
        bool left = dfs(root->left, p, q);//  Recursive left subtree , Judge its true value 
        bool right = dfs(root->right, p, q);//  Recursive right subtree , Judge its true value 
        if ( (left && right) || ((root->val == p->val || root->val == q->val) && (left || right))) {
     //  If the node has its target nodes on both sides , Or change the node itself to the target node , Its subtree in one direction contains another node , Then change the node to the nearest ancestor node 
            ancestor = root;//  Because it's from bottom to top , So the depth of the first discovery is the deepest , For the nearest ancestor node 
        }
        return left || right || (root->val == p->val || root->val == q->val);//  Return the true value according to the situation 
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
       dfs(root,p,q);
       return ancestor;
    }
};