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

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，那麼就來回顧一下：

圖片來源於維基百科（有這麼權威的資料，我就不自己瞎說了，逃……<喎?http://www.Bkjia.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;
    }
};