剑指offer 68-I与68-II


剑指offer 68-I 与 68-II

1.面试题68 - I. 二叉搜索树的最近公共祖先

利用二叉搜索树的性质。

class Solution {
public:
    // 二分搜索树
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return NULL;

        // p,q在root的左分支上
        if(root->val > p->val && root->val > q->val)
            return lowestCommonAncestor(root->left,p,q);
        // p,q在root的右分支上
        if(root->val < p->val && root->val < q->val)
            return lowestCommonAncestor(root->right,p,q);
        // 一个在左,一个在右
        return root;        
    }
};

2.面试题68 - II. 二叉树的最近公共祖先

根节点就是目标,那么可能是一上来就为p或q的其中一个输入,或者是分别存在于左右子树当中,则需要自上向下遍历搜索。

class Solution {
public:
    // 一般二叉树
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return NULL;
        if(root==p || root==q) return root;
        TreeNode* left = lowestCommonAncestor(root->left,p,q);
        TreeNode* right = lowestCommonAncestor(root->right,p,q);
        // 一边一个
        if(left&&right) {
            return root;
        } else if(left) {
            return left; // 都在左子树
        } else if(right) {
            return right; // 都在右子树
        } else {
            return NULL;
        }
    }
};

更多内容,订阅公众号

文章作者: light-city
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 light-city !
评论
  目录