865. 具有所有最深节点的最小子树

865. 具有所有最深节点的最小子树

# 865. 具有所有最深节点的最小子树
# 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 subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        res = self.maxDepth(root)
        return res.node 
        
    #  定义：输⼊⼀棵⼆叉树，返回该⼆叉树的最⼤深度以及最深叶⼦节点的最近公共祖先节点
    def maxDepth(self, root):
        if not root:
            return Result(None, 0)
        
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)

        # 当左右⼦树的最⼤深度相同时，这个根节点是新的最近公共祖先
        # 以当前 root 节点为根的⼦树深度是⼦树深度 + 1
        if left.depth == right.depth:
            return Result(root, left.depth+1)
        
        # 左右⼦树的深度不同，则最近公共祖先在 depth 较⼤的⼀边
        res = left if left.depth > right.depth else right
        # 正确维护⼆叉树的最⼤深度
        res.depth += 1

        return res 

class Result:
    def __init__(self, node, depth):
        # 记录最近公共祖先节点 node
        self.node = node
        # 记录以 node 为根的⼆叉树最⼤深度
        self.depth = depth

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39