Git原理之最近公共祖先 :: labuladong的算法小抄

[labuladong]

文章链接点这里：Git原理之最近公共祖先

评论礼仪 见这里，违者直接拉黑。

[Maxiah]

1650题：
方法一：套模板

class Solution {
public:
    Node* lowestCommonAncestor(Node* p, Node * q) {
        // 区别：本题没有根节点
        
        // 找到根节点
        Node *parent = p; // 从p开始找起
        while(parent->parent){
            if(parent == q){
                return parent;
            }
            parent = parent->parent;
        }

        return lca(parent,p,q);
    }
    Node* lca(Node* node,Node *p,Node *q){
        // base case
        if(node == nullptr){
            return nullptr;
        }

        if(node->val == p->val || node->val == q->val){
            return node;
        }
        Node *left = lca(node->left,p,q);
        Node *right = lca(node->right,p,q);
        if(left && right){
            return node;
        }

        return left == nullptr ? right : left;

    }
};

方法二：双链表相交问题

class Solution {
public:
    Node* lowestCommonAncestor(Node* p, Node * q) {
        // 双链表相交问题
        Node *a = p;
        Node *b = q;

        while(a!=b){
            a = a == nullptr ? q : a->parent;
            b = b == nullptr ? p : b->parent;
        }

        return a;
    }
};

[LebronHarden1]

写的好啊,东哥,力扣不是会员就很难受

[tanlandy]

Python 代码，附注释和时空复杂度

236. Lowest Common Ancestor of a Binary Tree

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        """
        解题思路：每个节点要知道什么、做什么：什么时候做
        遍历or递归
        要知道自己的子树里是否有这两个数字->递归
        要做什么：返回自己子树是否有这两个数字->递归
        什么时候做：后序遍历，传递子树信息

        自下而上，这个函数就返回自己左右子树满足条件的node：返回自己或者不为None的一边。base case就是找到了
        如果一个节点能够在它的左右子树中分别找到 p 和 q，则该节点为 LCA 节点。

        时间：O(N)
        空间：O(N)
        """
        if root is None: # base case
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        
        # 后序遍历
        if root == p or root == q: # Case 1：公共祖先就是我自己，也可以放在前序位置（要确保p,q在树中）
            return root
        
        if left and right: # Case 2：自己子树包含这两个数
            return root
        else:
            return left or right # Case 3：

1676. Lowest Common Ancestor of a Binary Tree IV

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', nodes: 'List[TreeNode]') -> 'TreeNode':
        """
        和LC236类似，只是检查公共祖先就是我自己的时候有变化

        Time: O(N)
        Space: O(N)
        """
        nodes_set = set(nodes)
        
        def dfs(node):
            if node is None:
                return None
            if node in nodes_set: # 可在前序位置，也可后
                return node
            
            left = dfs(node.left)
            right = dfs(node.right)
            
            if left and right:
                return node
            else:
                return left or right
        
        return dfs(root)

1644. Lowest Common Ancestor of a Binary Tree II

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        """
        Node不一定在树里，当root == p or root == q必须后序遍历判断
        dfs() 除了返回当前节点外，还返回是否存在
        
        Time: O(N)
        Space: O(N)
        """
        def dfs(root):
            if not root:
                return None, False
            
            left, l_exist = dfs(root.left)
            right, r_exist = dfs(root.right)
            
            if root == p or root == q:
                return root, left or right
            
            if left and right:
                return root, True
            else:
                if left:
                    return left, l_exist
                else:
                    return right, r_exist
                 
        lca, exist = dfs(root)
        if not exist:
            return None
        return lca

235. Lowest Common Ancestor of a Binary Search Tree

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        """
        不需要去遍历子树，由于 BST 左小右大的性质，将当前节点的值与 val1 和 val2 作对比即可判断当前节点是不是 LCA

        Time: O(H)
        Space: O(1)
        """
        cur = root
        
        while cur:
            # cur太小就往右
            if p.val > cur.val and q.val > cur.val:
                cur = cur.right
            # cur太大就往左
            elif p.val < cur.val and q.val < cur.val:
                cur = cur.left
            else: # p.val <= cur.val <= q.val
                return cur

1650. Lowest Common Ancestor of a Binary Tree III

    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        """
        先求各自深度，再把深的往上走直到当前深度相同，最后一起往上走找parent；注意找深度是while p；深度就是层数root的深度是1

        时间：O(H)
        空间：O(1)
        """

        # get_depth(p) 返回节点p的深度
        def get_depth(p):
            depth = 0
            while p:
                p = p.parent
                depth += 1
            return depth
    
        d1 = get_depth(p)
        d2 = get_depth(q)
        
        # 把更深的往上走，直到相同深度
        while d1 > d2:
            p = p.parent
            d1 -= 1
                
        while d1 < d2:
            q = q.parent
            d2 -= 1
        
        # 现在在相同深度，一起往上走找LCA
        while p != q:
            p = p.parent
            q = q.parent
        
        return p      

[MzxlM]

"因为题目说了p和q一定存在于二叉树中(这点很重要），所以即便我们遇到q就直接返回，根本没遍历到p，也依然可以断定p在q底下，q就是LCA节点。"
我觉得情况二下面这个会引起歧义，我思考了很久觉得 应该是 我们在左侧遇见了q 直接返回 没遍历到左侧下面的q。 但是遍历完整了右侧发现没有找到，那么他就一定在左侧下面，q就是lca节点

[zhiming429438709]

python写法和题解保持一致

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        self.findp = False
        self.findq = False
        res = self.find(root, p, q)
        if self.findp and self.findq:
            return res
        return None
    
    def find(self, root, p, q):
        if root is None: # base case
            return None

        left = self.find(root.left, p, q)
        right = self.find(root.right, p, q)
        
        # 后序遍历
        if root == p or root == q: # Case 1：公共祖先就是我自己，也可以放在前序位置（要确保p,q在树中）
            if root == p:
                self.findp = True
            if root == q:
                self.findq = True
            return root
        
        if left and right: # Case 2：自己子树包含这两个数
            return root
        if left is None and right is None:
            return None
        return left if left else right

[Goolloo]

Note:
236的解法，当LCA是pq其中一点情况时，会跳过剩余的子树。
检查pq找到以后直接返回的解法，必须搜索到pq两个node，但是能跳过剩余未搜索的树。
两种解法互相有tradeoff，没有完美解🙃

[LeeHaruYa]

滴滴滴打卡

[jxs1211]

postorder solution of go version

func find(root *TreeNode, p, q int) *TreeNode {
    if root == nil {return nil}
    if root.Val == p || root.Val == q {
        return root
    }
    l := find(root.Left, p, q)
    r := find(root.Right, p, q)
    if l != nil && r != nil {
        return root
    }
    if l != nil {return l}
    return r
}
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    return find(root, p.Val, q.Val)
}

[zhangjunmengyang]

秋招冲刺打卡