LeetCode：236. The nearest common ancestor of 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 .

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, 10^5] Inside .
• -10^9 <= Node.val <= 10^9
• all Node.val Different from each other .
• p != q
• p and q All exist in a given binary tree .

---

Their thinking

1. First use recursion ：root yes null perhaps root be equal to p or q, explain root yes p,q The common ancestor of （ Recursion ends ）, So as to recurse the left and right subtrees
2. Then judge after the recursion of the left and right subtrees

• If the left and right subtree recursive functions do not return empty , be root Namely p,q The common ancestor of
• If the value returned by the left subtree recursive function is null , be p,q All in the right subtree , Go straight back to right that will do
• If the value returned by the right subtree recursive function is null , be p,q It's all in zuozhu , Go straight back to left that will do

Code

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */
/** * @param {TreeNode} root * @param {TreeNode} p * @param {TreeNode} q * @return {TreeNode} */
var lowestCommonAncestor = function(root, p, q) {
    
    const travelTree = function(root, p, q) {
    
        //  Recursive termination condition 
        if(root === null || root === p|| root === q) {
    
            return root;
        }
        let left = travelTree(root.left, p, q);
        let right = travelTree(root.right, p, q);
      	// If you can find both the left and right subtrees of a node p and q, This indicates that this node is a common ancestor 
        if(left !== null && right !== null) {
    
            return root;
        }
        if(left === null) {
    
            return right;
        }
        return left;
    }
    return travelTree(root, p, q);
};