# LCA of BST

### 描述​

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;    }}