程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode 235 Lowest Common Ancestor of a Binary Search Tree(二叉搜索樹的最小公共祖先)

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

編輯:C++入門知識

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved