二叉树的最近公共祖先问题

前端之家收集整理的这篇文章主要介绍了二叉树的最近公共祖先问题前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

一、普通二叉树的公共祖先问题

/**
 * 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) {
        //求最近公共祖先,如果可以自底向上搜索就好了,正好,后序遍历就是自底向上的,所以采用后序递归遍历框架
        递归终止条件base case
        if(root == nullptr)
            return nullptr;
        if(root == p || root == q)
             root;
        要遍历整棵树,先把递归的结果存起来,下面进行逻辑处理
        TreeNode* left = lowestCommonAncestor(root->left,p,q);
        TreeNode* right = lowestCommonAncestor(root->right,q);
        如果p和q都在以root为根的树中,那么left好right一定是p和q(从base case得出)
        if(left != nullptr && right !=如果p和q都不在以root为根的树中
        if(left == nullptr && right ==剩下的就是q和q只有一个存在与以root为根的树中,函数返回该节点
        return left == nullptr? right : left;
    }
};

二、二叉搜索树的公共祖先问题

相比于普通二叉树,二叉搜索树有一些特性,可以利用这些特性来改善算法性能

因为二叉树搜索树的特性,其实只要从上到下遍历的时候,遍历的当前节点数值在[p,q]区间中说明该节点就是最近公共祖先了。

*/

虽然按题意不会出现但还是判断一下吧养成一个良好的习惯
        搜索一条边,因为是二叉搜索树,如果在这条边中,找到后直接返回
        if(root->val > p->val && root->val > q->val) {
            TreeNode* left = lowestCommonAncestor(root->if(left != nullptr)
                 left;
        }
        if(root->val < p->val && root->val < q->val) {
            TreeNode* right = lowestCommonAncestor(root->if(right != right;
        }
        剩下的几种情况就是root就在[p,q]区间里了,直接返回即可
         root;
    }
};

 

猜你在找的算法相关文章