The title

Given a binary search tree, find the most recent common ancestor of two specified nodes in the tree.

The definition of the nearest common ancestor in Baidu encyclopedia is: “For the two nodes P and Q with root tree T, the nearest common ancestor is expressed as a node X, satisfying that X is the ancestor of P and Q and x is as deep as possible (a node can also be its own ancestor).

For example, given the following binary search tree: root = [6,2,8,0,4,7,9, null, null, 3, 5)

 

Example 1:

Input: root = [6,2,8,0,4,7,9, null, null, 3, 5), p = 2, q = 8 output: 6: node 2 and 8 of recent common ancestor is 6.Copy the code

Source: LeetCode leetcode-cn.com/problems/er…

Their thinking

  • Ancestor: All nodes along the path from a node’s parent to its root are its ancestors
  • Nearest common ancestor: the two nodes P and q intersect the two paths of the root node. The starting node is the nearest common ancestor. In the example:
    • 6 is the ancestor of 3 and 5, but not the most recent common ancestor, because 6’s left child node 2 is also their ancestor
    • 2 is the ancestor of 3 and 5, but not the most recent common ancestor either, because 2’s right child node 4 is also their ancestor
    • 4 is the ancestor of 3 and 5, and the left and right child nodes of 4 are not their ancestors, so 4 is the closest common ancestor of 3 and 5
    • According to the above inference, when a node on the ancestor chain of P and Q is not the ancestor of P and Q, the node is the nearest common ancestor

According to the characteristics of the binary search tree, the value of the root is greater than any node of the left subtree and less than any node of the right subtree, then:

  • When the root node is greater than the values of P and q, the nearest ancestor is in the left subtree
  • When the root node is less than the values of P and q, the nearest ancestor is in the right subtree
  • In either case, the root is the nearest ancestor

Code implementation

var lowestCommonAncestor = function(root, p, q) {
    if (root.val < p.val && root.val < q.val) {
        return lowestCommonAncestor(root.right, p, q)
    } else if (root.val > p.val && root.val > q.val) {
        return lowestCommonAncestor(root.left, p, q)
    }

    return root
};
Copy the code

If there are mistakes welcome to point out, welcome to discuss together!