Topic describes

Topic link

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

Example 2:

Input: root = [6,2,8,0,4,7,9, null, null, 3, 5), p = 2, q = 4 output: 2: recent common ancestor node 2, and 4 is 2, because recent common ancestor nodes can be according to the definition for the node itself.Copy the code

Description:

  • All nodes have unique values.
  • P and Q are different nodes and exist in the given binary search tree.

Answer key

Using the characteristics of binary search tree, first judge whether P and Q are equal, if they are equal, then directly return either P or Q, the end of the program

If not, then determine whether P and Q agree on whether to go left or right

If both p and q are less than root and both brothers agree to go left 👈, then root = root.left

If p and q are both greater than root and both brothers agree that 👉 is to the right, then root = root.right

If p and Q have differences on the next route, it means that P and Q will go their separate ways at the current node, and the current root is the last station that the two brothers will go together before parting

Return the current root, the program ends

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return None
        if p.val == q.val:
            return p
        while root:
            if root.val < q.val and root.val < p.val:
                root = root.right
            elif root.val > q.val and root.val > p.val:
                root = root.left
            else:
                return root
Copy the code
var lowestCommonAncestor = function (root, p, q) {
    if(! root) {return null
    }
    if (p.val === q.val) {
        return q
    }
    while (root) {
        if (root.val < q.val && root.val < p.val) {
            root = root.right
        }
        else if (root.val > q.val && root.val > p.val) {
            root = root.left
        }
        else {
            return root
        }
    }
};
Copy the code