剑指 Offer 68 - 二叉树的最近公共祖先

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

在二叉搜索树中，公共祖先一定是从根节点往下查找的过程中，第一个值介于两节点值之间的节点

非递归版

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

递归版

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* cur, TreeNode* p, TreeNode* q) {
        int big = max(p->val, q->val);
        int small = min(p->val, q->val);
        if(!cur || (cur->val >= small && cur->val <= big)){
            return cur;
        }

        if(cur->val < small){
            return lowestCommonAncestor(cur->right, p, q);
        }else{
            return lowestCommonAncestor(cur->left, p, q);
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

剑指 Offer 68 - II. 二叉树的最近公共祖先

祖先的定义： 若节点 p 在节点 root 的左（右）子树中，或 p = root ，则称 root 是 p 的祖先
最近公共祖先的定义： 设节点 root 为节点 p,q 的某公共祖先，若其左子节点 root.left 和右子节点 root.right 都不是 p,q 的公共祖先，则称 root 是 “最近的公共祖先”

根据以上定义，若 root 是 p,q 的 最近公共祖先 ，则只可能为以下情况之一：

1. p 和 q 在 root 的子树中，且分列 root 的 异侧（即分别在左、右子树中）；
2. p=root ，且 q 在 root 的左或右子树中；
3. q=root ，且 p 在 root 的左或右子树中；

考虑通过递归对二叉树进行先序遍历，当遇到节点 p 或 q 时返回。从底至顶回溯，当节点 p,q 在节点 root 的异侧时，节点 root 即为最近公共祖先，则向上返回 root

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

        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(nullptr != left && nullptr != right){
            // p q在root的两侧，则root为最近公共祖先
            return root;
        }
        return nullptr == left ? right : left;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

参考题解