LeetCode/solutions/235. Lowest Common Ancestor of a Binary Search Tree.md

235. Lowest Common Ancestor of a Binary Search Tree

思路

求一棵搜索树(BST)中两个节点的最低公共祖先( lowest common ancestor, LCA).
求二叉树中节点的最低公共祖先比较麻烦(要用到非递归的后序遍历算法)，但是这里是搜索树，由于搜索树中的节点是排好序的，所以这题就简单了。
若有前提p < q, 那么一共有三种情况:

• 若p > root, 说明LCA应该在root的右子树内;
• 若q < root, 说明LCA应该在root的左子树内;
• 否则，即 p < root < q, 那么root就是LCA。(递归出口)

由此可见很容易写出一个递归算法。不过也可以很容易用while循环实现，见下面的代码。

C++

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode *tmp;
        if(p -> val > q -> val){ // 保证 p -> val <= q -> val
            tmp = q;
            q = p;
            p = tmp;
        }
        tmp = root;
        while(tmp){
            if(p -> val > tmp -> val) tmp = tmp -> right;
            else if(q -> val < tmp -> val) tmp = tmp -> left;
            else return tmp;
        }
    }
};