程序员面试金典-0408-首个共同祖先

╰+攻爆jí腚メ 2022-10-25 12:57 132阅读 0赞

## 程序员面试金典-0408-首个共同祖先 ##

设计并实现一个算法，找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。注意：这不一定是二叉搜索树。
    
    例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
    
        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4
    示例 1:
    
    输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
    输出: 3
    解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
    示例 2:
    
    输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
    输出: 5
    解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
    说明:
    
    所有节点的值都是唯一的。
    p、q 为不同节点且均存在于给定的二叉树中。
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/first-common-ancestor-lcci
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

struct TreeNode * lowestCommonAncestor_helper(struct TreeNode * root, struct TreeNode * p,struct TreeNode * q);
    bool covers(struct TreeNode * root, struct TreeNode * p);
    struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q){
        
       if(!covers(root,p) || !covers(root,q))
            return NULL;
        return lowestCommonAncestor_helper(root,p,q); 
    }
    
    bool covers(struct TreeNode * root, struct TreeNode * p){
        
        if(root==NULL)
            return false;
        if(root == p)
            return true;
        return covers(root->left,p) || covers(root->right,p);
    }
    
    struct TreeNode * lowestCommonAncestor_helper(struct TreeNode * root, struct TreeNode * p,struct TreeNode * q){
        
        if(root == NULL)
            return NULL;
        if(root == p || root == q)
            return root;
        bool is_p_on_left = covers(root->left,p);
        bool is_q_on_left = covers(root->left,q);
        if(is_p_on_left != is_q_on_left)
            return root;
        struct TreeNode * child_side = is_p_on_left? root->left : root->right;
        return lowestCommonAncestor_helper(child_side,p,q);
    }