Description

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given 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
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Note:

  • All of the nodes’ values will be unique.
  • p and q are different and both values will exist in the BST.

Solutions

1. 迭代

  因为没有刷过类似的问题,在参考了 Discussion 后就恍然大悟了。其实这里考察的是 BST 的特性,比当前节点小的结点放左边,比当前节点大的放右边。我们的目标是要找到一个节点,其是给定两个结点的最近共同祖先,最近指的是离两者的距离最小。那么可以将 root,p,q 三个结点的大小情况分开考虑:

1、root > max(p, q)

  即此时节点 p,q 都在当前结点 root 的右子树下,虽然 root 是其共同祖先,但并不是其最近的共同祖先,于是需要继续从右子树向下深入探索。

2、root < max(p, q)

  类似的,此种情况是节点 p,q 都在当前结点 root 的左子树下,于是还得继续从左子树继续向下深入探索。

3、(p < root < q) or (q < root < p)

  当出现这类大小关系时,根据 BST 的特性,我们能够判断此时 root 就是节点 p 和 q 的最近共同祖先。

# Time: O(logn)
# Space: O(logn)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return root
        
        while root:
            if p.val < root.val > q.val:
                root = root.left
            elif p.val > root.val < q.val:
                root = root.right
            else:
                return root

# 27/27 cases passed (72 ms)
# Your runtime beats 93.32 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (16.7 MB)

2. 递归

  下面这种理解需要一定的想法,注意在迭代的时候要考虑怎么用迭代的函数。

# Time: O(logn)
# Space: O(logn)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root
        
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        return root if left and right else left or right

# 27/27 cases passed (92 ms)
# Your runtime beats 24.51 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (16.7 MB)
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root
        
        if min(p.val, q.val) < root.val < max(p.val, q.val):
            return root
        elif root.val > max(p.val, q.val):
            return self.lowestCommonAncestor(root.left, p, q)
        elif root.val < min(p.val, q.val):
            return self.lowestCommonAncestor(root.right, p, q)

References

  1. 235. Lowest Common Ancestor of a Binary Search Tree
  2. 50 剑指 Offer