235. Lowest Common Ancestor of a Binary Search Tree

如果p, q的值比root都小就去左边找，反之。如果pq有一方的值等于root，或者pq分散在root的两边，直接一路返回root的值。

recursion:

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (p.val < root.val && q.val < root.val) {
        return lowestCommonAncestor(root.left, p, q);
    } else if (p.val > root.val && q.val > root.val) {
        return lowestCommonAncestor(root.right, p, q);
    } 
    return root; 
}

iteration:

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while (root != null) {
        if (p.val < root.val && q.val < root.val) {
            root = root.left;
        } else if (p.val > root.val && q.val > root.val) {
            root = root.right;
        }
        return root;
    }
    return null;
}