翻译

给定一个二叉搜索树(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,那么就来回顾一下:

这里写图片描述

图片来源于维基百科(有这么权威的资料,我就不自己瞎说了,逃……<喎"http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPrKpv823os3q1q6687eiz9bNvMasv7Syu8flwcujrMTHvs2w0c7E19a92tGhz8LAtLrDwcujrHRoYW5rc6OsV2lraXBlZGlho6E8L3A+DQo8cHJlIGNsYXNzPQ=="brush:java;"> 二叉查找树(英语: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;
    }
};