视频学习记录

https://www.bilibili.com/video/BV1W44y1Z7AR

  • 本次专注于“最近公共祖先”，核心就是聚焦一个节点分类讨论，当要找的节点在其左右，或者自己就是要怎么处理，其他详细内容在代码注释中。

例题和课后作业代码记录

236. 二叉树的最近公共祖先

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 分类讨论一下：找p和q的最近公共祖先，包括p和q自身，所以如果找到p或者q就直接返回对应节点
        # 如果另一个节点在找到的那个下面，那正好一起了；如果在另一边，就会在上面产生一个节点左右都有值
        # 那这个都有值的节点就是答案，返回即可。
        # 那么对于普通节点，如果左边有值，就得检查右边有没有值，没有的话，只返回左边；
        # 左边没值的话，无论右边是否空都返回右边，毕竟一样
        # 时间：On，最坏情况下还得遍历整个树
        # 空间：On，最坏情况下递归嵌套n个
        if not root or root is p or root is q:
            return root # 同时解决边缘为空，以及正好找到pq两点的情况
        l = self.lowestCommonAncestor(root.left, p, q)
        r = self.lowestCommonAncestor(root.right, p, q)
        if not l:
            return r 
        return root if l and r else l # 这里复合了右边没有的情况和两边都有的情况

235. 二叉搜索树的最近公共祖先

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 时间：On，最坏情况下还得遍历整个树
        # 空间：On，最坏情况下递归嵌套n个
        # 与普通二叉树的最近公共祖先相比，这里可以利用二叉搜索树的性质更快地找到这个祖先
        # 对于一个节点，如果p和q分别在两侧，那么当前节点一定是最近公共祖先，因为当前节点的左右子树各涵盖不了另一个。
        # 如果pq同侧，那就只遍历那一边即可，而且找到其中一个就能立刻返回，因为这种遍历说明都是一侧的，另一个一定在下面
        if root is p or root is q: # p 和 q 必然存在的情况下，这个遍历方式不可能遇到空
            return root 
        x = root.val 
        
        if p.val < x and q.val < x:
            return self.lowestCommonAncestor(root.left, p, q)
        
        if p.val > x and q.val > x:
            return self.lowestCommonAncestor(root.right, p, q)

        return root # 这里复合了p和q分别在root两侧的情况

1123. 最深叶节点的最近公共祖先

https://leetcode.cn/problems/lowest-common-ancestor-of-deepest-leaves/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # 有个想法，后序遍历，让每个节点处理左右收到的最大深度，返回其中深度较大的一边
        # 如果两边深度一样，说明当前节点就是最近公共祖先
        # 时间：On，最坏情况下还得遍历整个树
        # 空间：On，最坏情况下递归嵌套n个
        def dfs(root, carry):
            carry += 1
            if not root:
                return carry, root 
            l_depth, l_node = dfs(root.left, carry)
            r_depth, r_node = dfs(root.right, carry)
            if l_depth == r_depth: # 要么是叶节点，要么是两边真的有相同深度的叶节点
                return l_depth, root 
            return (l_depth, l_node) if l_depth > r_depth else (r_depth, r_node)
        return dfs(root, 0)[1]