LeetCode 235 Lowest Common Ancestor of a Binary Search Tree（二叉搜索树的最小公共祖先）

翻译

给定一个二叉搜索树（BST），找出两个给定节点的最小公共祖先（LCA）。

根据维基百科对于LCA的定义：“最小公共祖先的定义是对于两个节点v和s有一个最小的节点T，
以至于v和s都是T的后代（其中我们允许节点是自身的后代）。”
        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5
例如，对于节点2和8的最小公共祖先是节点6.

另一个是2和4的LCA是2，因为根据LCA的定义，一个节点的是自身是后代。

原文

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined 

between two nodes v and w as the lowest node in T that has both v and w as descendants 

(where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. 
Another example is LCA of nodes 2 and 4 is 2, 
since a node can be a descendant of itself according to the LCA definition.

分析

这个时候一定要先知道什么是BST，那么就来回顾一下：

图片来源于维基百科（有这么权威的资料，我就不自己瞎说了，逃……

博客发完之后发现图片看不清了，那就把文字节选下来好了，thanks，Wikipedia！

二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树（英语：ordered binary tree），排序二叉树（英语：sorted binary tree），
是指一棵空树或者具有下列性质的二叉树：
若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
任意节点的左、右子树也分别为二叉查找树；
没有键值相等的节点。

还是用擅长的递归吧，我好慌，每次都是效率不行的递归。

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == p || root == q) return root;
    if (root == NULL || p == NULL || q == NULL) return NULL;

    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;
}

根据LCA的定义，可以是节点自身，那么如果相等的话就可以直接返回啦。

如果任何一个为空了，结果不也为空么？

其余的两种情况，对应这个图来看看。对于3和5，如果（2）比它们都小，那就应该往右走了；对于0和2，如果（6）比它们都大，那就应该往左走了；对于3和7，如果（6）在它们中间，那就直接返回了。

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

再高级的解法我还没想到，以后再补充~

代码

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == p || root == q) return root;
        if (root == NULL || p == NULL || q == NULL) return NULL;

        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;
    }
};