My Forty-Second Page - 二叉搜索树的最近公共祖先 - By Nicolas

这篇page主要是针对leetcode上的235.二叉搜索树的最近公共祖先所写的。小尼先简单的说明一下这道题的意思，给出一个二叉搜索树，找到该树种两个指定节点的最近公共祖先。首先这是一个二叉搜索树，其实这道题给我们已经提供了遍历的顺序，其实我们的思路也很简单。

小尼接下来讲一下思路，根据题目的条件，条件给出root节点，p节点，q节点，其实也就两种情况，如果q在root左子树中，q在右子树中，那么我们直接返回root就可以了。第二种情况就是p和q都在root节点的一边（也就是都在左子树或者都在右子树），小尼给出第一种解法递归的解法，小尼先拉一下代码：

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

上诉的代码就是判断一下这三个节点的val值的大小，然后再做出递归

小尼接下来拉一下迭代法的代码：

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

其实思路和第一种递归的方法是一眼的，只是区别在于这里利用判断是否为true的方法写了一个while循环，这里的根上述的递归起了相同的作用，其实迭代就是一种循环的体现。