### 描述

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

      _______6______
/              \
___2__          ___8__
/      \        /      \
1      _4       7       9
/  \
3   5


For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

### 分析

1. 两个子节点都在树的左子树上
2. 两个子节点都在树的右子树上
3. 一个子节点在左子树，一个子节点在右子树
4. 一个子节点的值和根节点的值相等

### 解法1 递归

// LCA of BST
// Time Complexity: O(h), Space Complexity: O(h)
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;

if (Math.max(p.val, q.val) < root.val) {
return lowestCommonAncestor(root.left, p, q);
} else if (Math.min(p.val, q.val) > root.val) {
return lowestCommonAncestor(root.right, p, q);
} else {
return root;
}
}
}

### 解法2 迭代

// LCA of BST
// Time Complexity: O(h), Space Complexity: O(1)
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (root != null) {
if (Math.max(p.val, q.val) < root.val) {
root = root.left;
} else if (Math.min(p.val, q.val) > root.val) {
root = root.right;
} else {
return root;
}
}
return null;
}
}