fucking-algorithm
fucking-algorithm copied to clipboard
Published
20 hours ago •
labuladong
labuladong
Git原理之最近公共祖先 :: labuladong的算法小抄
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;
}
};
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
"因为题目说了p和q一定存在于二叉树中(这点很重要），所以即便我们遇到q就直接返回，根本没遍历到p，也依然可以断定p在q底下，q就是LCA节点。" 我觉得情况二下面这个会引起歧义，我思考了很久觉得 应该是 我们在左侧遇见了q 直接返回 没遍历到左侧下面的q。 但是遍历完整了右侧发现没有找到，那么他就一定在左侧下面，q就是lca节点
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
Note: 236的解法，当LCA是pq其中一点情况时，会跳过剩余的子树。 检查pq找到以后直接返回的解法，必须搜索到pq两个node，但是能跳过剩余未搜索的树。 两种解法互相有tradeoff，没有完美解🙃
