class Solution {
    // 递归宏观语义:返回以root为根节点的二分搜索树中 结点p和q的最近公共祖先结点
    // 时间复杂度O(N)  空间复杂度O(N)
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {  // 题目已经明确说明 p q在二分搜索树中
            return null;   
        }
        if (p.val < root.val && q.val < root.val) { // p,q都在左子树中
            return lowestCommonAncestor(root.left, p, q); // 递归到左子树去找p，q的最近公共祖先
        }
        if (p.val > root.val && q.val > root.val) { // p,q都在右子树中
            return lowestCommonAncestor(root.right, p, q); // 递归到右子树去找p，q的最近公共祖先
        }
        // return root包含一下几种情况
        // 1. p,q在root两侧，那么最近公共祖先结点就是root
        // 2. p就是根结点 q在左子树或右子树  最近公共祖先结点就是root
        // 3. q就是根结点 p在左子树或右子树  最近公共祖先结点就是root
        return root;
    }
}

class Solution {
    // 根递归的思路类似
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        TreeNode curNode = root;
        while (curNode != null) {
            if (p.val < curNode.val && q.val < curNode.val) { // 最近公共结点在左子树
                curNode = curNode.left;
            }else if (p.val > curNode.val && q.val > curNode.val) { // 最近公共结点在右子树
                curNode = curNode.right;
            }else{
                // return curNode包含一下几种情况
                // 1. p,q在curNode两侧，那么最近公共祖先结点就是curNode
                // 2. p就是根结点 q在左子树或右子树  最近公共祖先结点就是curNode
                // 3. q就是根结点 p在左子树或右子树  最近公共祖先结点就是curNode
                return curNode;
            }
        }
        return null;
    }
}