## 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)