01. 二叉搜索树的最近公共祖先

235. 二叉搜索树的最近公共祖先

• 当我们从上向下去递归遍历，第一次遇到 cur节点是数值在[p, q]区间中，那么cur就是 p和q的最近公共祖先；
• 当前节点的值都小于p、q值，说明最近公共祖先在当前节点右边；
• 当前节点的值都大于p、q值，说明最近公共祖先在当前节点左边。

class Solution {
    // 方法1：递归
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(root.val < q.val && root.val < p.val) {
            return lowestCommonAncestor(root.right,p,q); // 说明节点在右子树中
        }else if(root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left,p,q); // 说明节点在左子树中
        }
        return root;
    }

    // 方法2：迭代
    public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p, TreeNode q) {
        if(root == null) return null;
        while(root != null) {
            if(root.val < q.val && root.val < p.val){
                root = root.right;
            }else if(root.val > p.val && root.val > q.val) {
                root = root.left;
            }else {
                return root;
            }
        }
        return null;
    }

}