235. 二叉搜索樹的最近公共祖先

一、題目

給定一個二叉搜索樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。

百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點 p、q，最近公共祖先表示為一個結(jié)點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）?！?/p>

例如，給定如下二叉搜索樹: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
輸出: 6 
解釋: 節(jié)點 2 和節(jié)點 8 的最近公共祖先是 6。

示例 2:

輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
輸出: 2
解釋: 節(jié)點 2 和節(jié)點 4 的最近公共祖先是 2, 因為根據(jù)定義最近公共祖先節(jié)點可以為節(jié)點本身。

說明:

• 所有節(jié)點的值都是唯一的。
• p、q 為不同節(jié)點且均存在于給定的二叉搜索樹中。

二、題解

方法一：遞歸

我們需要充分利用二叉搜索樹的性質(zhì)，即左子樹的所有節(jié)點值都小于根節(jié)點值，右子樹的所有節(jié)點值都大于根節(jié)點值。這個性質(zhì)可以幫助我們有效地縮小搜索范圍。

算法思路

1. 首先，我們要考慮一種簡單情況：如果根節(jié)點的值大于節(jié)點 p 和 q 的值，那么說明 p 和 q 位于根節(jié)點的左子樹中，因為左子樹的所有節(jié)點值都小于根節(jié)點值。我們可以在根節(jié)點的左子樹上繼續(xù)搜索 p 和 q 的最近公共祖先。

2. 同樣，如果根節(jié)點的值小于節(jié)點 p 和 q 的值，那么說明 p 和 q 位于根節(jié)點的右子樹中，因為右子樹的所有節(jié)點值都大于根節(jié)點值。我們可以在根節(jié)點的右子樹上繼續(xù)搜索 p 和 q 的最近公共祖先。

3. 但是，如果根節(jié)點的值介于節(jié)點 p 和 q 的值之間，或者根節(jié)點的值等于其中一個節(jié)點的值，那么說明 p 和 q 分別位于根節(jié)點的左右子樹中，此時根節(jié)點就是它們的最近公共祖先。

4. 我們可以利用遞歸來實現(xiàn)這個過程，根據(jù)上述的思路，遞歸搜索左子樹和右子樹，最終找到最近公共祖先。

具體實現(xiàn)

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) return nullptr;

        if (root->val > p->val && root->val > q->val) {
            TreeNode* left = lowestCommonAncestor(root->left, p, q);
            return left;
        }
        if (root->val < p->val && root->val < q->val) {
            TreeNode* right = lowestCommonAncestor(root->right, p, q);
            return right;
        }
        
        return root;
    }
};

算法分析

時間復雜度

• 在每個遞歸步驟中，我們都會根據(jù)節(jié)點的值來決定是繼續(xù)在左子樹搜索還是在右子樹搜索，所以每次遞歸都會剔除一半的節(jié)點。因此，算法的時間復雜度為 O(log N)，其中 N 是樹中節(jié)點的總數(shù)。

空間復雜度

• 遞歸調(diào)用棧的最大深度取決于樹的高度，對于平衡的二叉搜索樹，空間復雜度為 O(log N)；對于不平衡的樹，最壞情況下的空間復雜度為 O(N)，其中 N 是樹中節(jié)點的總數(shù)。

方法二：迭代

簡單來說，就是把上面的遞歸思路用迭代方式寫一遍：文章來源地址http://www.zghlxwxcb.cn/news/detail-652737.html

/**
 * 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) {
        while(root){
            if(root->val > p->val && root->val > q->val){
                root = root->left;
            }else if(root->val < p->val && root->val < q->val){
                root = root->right;
            }else{
                return root;
            }
        }
        return root;
    }
};

到了這里，關(guān)于LeetCode235. 二叉搜索樹的最近公共祖先的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！