仰望星空

位我上者，灿烂星空；道德律令，在我心中。

0%

二叉树公共祖先问题

发表于 更新于 分类于 ，
本文字数： 1k 阅读时长 ≈ 1 分钟

【道德经·第三十八章·中】故失道而后德，失德而后仁，失仁而后义，失义而后礼。夫礼者，忠信之薄，而乱之首。前识者，道之华，而愚之始。

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return nullptr;
        
        if(root==p || root==q) {
            return root;
        }
        
        TreeNode *l = lowestCommonAncestor(root->left, p, q);
        TreeNode *r = lowestCommonAncestor(root->right, p, q);
        
        if(l && r) {
            return root;
        }
        
        if(!l && !r) {
            return nullptr;
        }
        
        return l==nullptr ? r : l;
    }
};

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

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return root;
        
        TreeNode *cur = root;
        while(cur) {
            if(cur->val>p->val && cur->val>q->val) {
                cur = cur->left;
            } else if(cur->val<p->val && cur->val<q->val) {
                cur = cur->right;
            } else {
                break;
            }
        }
        
        return cur;
    }
};

位我上者，灿烂星空；道德律令，在我心中。