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

难度: Medium

给定一个根为 root 的二叉树，每个节点的深度是 该节点到根的最短距离 。

返回包含原始树中所有 最深节点 的 最小子树 。

如果一个节点在 整个树 的任意节点之间具有最大的深度，则该节点是 最深的 。

一个节点的子树是该节点加上它的所有后代的集合。

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4]
输出：[2,7,4]
解释：
我们返回值为 2 的节点，在图中用黄色标记。
在图中用蓝色标记的是树的最深的节点。
注意，节点 5、3 和 2 包含树中最深的节点，但节点 2 的子树最小，因此我们返回它。

示例 2：

输入：root = [1]
输出：[1]
解释：根节点是树中最深的节点。

示例 3：

输入：root = [0,1,3,null,2]
输出：[2]
解释：树中最深的节点为 2 ，有效子树为节点 2、1 和 0 的子树，但节点 2 的子树最小。

提示：

树中节点的数量在 [1, 500] 范围内。
0 <= Node.val <= 500
每个节点的值都是 独一无二 的。

注意：本题与力扣 1123 重复：https://leetcode-cn.com/problems/lowest-common-ancestor-of-deepest-leaves

Submission

运行时间: 25 ms

内存: 0.0 MB

# 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:
        
        def traverse(node):
            if not node:
                return (None, 0)
            left, leftHeight = traverse(node.left)
            right, rightHeight = traverse(node.right)

            if leftHeight == rightHeight:
                return (node, leftHeight + 1)
            elif leftHeight < rightHeight:
                return (right, rightHeight + 1)
            else:
                return (left, leftHeight + 1) 
        node, h = traverse(root)
        return node

Explain

使用后序遍历的方式遍历二叉树。在遍历过程中，记录每个节点的高度，并比较左右子树的高度。如果左右子树高度相等，则当前节点就是最小子树的根节点；如果左子树高度大于右子树，则最小子树的根节点在左子树中；反之则在右子树中。最后返回最小子树的根节点。

时间复杂度: O(n)

空间复杂度: O(n)

# 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:
        
        def traverse(node):
            if not node:
                # 如果当前节点为空，返回 None 和高度 0
                return (None, 0)
            
            # 递归遍历左子树，得到左子树的最小子树根节点和高度
            left, leftHeight = traverse(node.left)
            # 递归遍历右子树，得到右子树的最小子树根节点和高度
            right, rightHeight = traverse(node.right)

            if leftHeight == rightHeight:
                # 如果左右子树高度相等，则当前节点就是最小子树的根节点
                return (node, leftHeight + 1)
            elif leftHeight < rightHeight:
                # 如果右子树更高，则最小子树的根节点在右子树中
                return (right, rightHeight + 1)
            else:
                # 如果左子树更高，则最小子树的根节点在左子树中
                return (left, leftHeight + 1) 
        
        # 从根节点开始遍历二叉树
        node, h = traverse(root)
        # 返回最小子树的根节点
        return node

Explore

在处理只有一个节点的树时，由于该节点既是根节点也是叶子节点，因此没有左子树和右子树。在递归函数`traverse`中，首先会检查当前节点是否存在，对于单节点树，该节点存在，然后对其左右子树进行递归调用。由于这两个子树都不存在，递归调用会立即返回`(None, 0)`。随后，该函数会比较左右子树的高度，都是0，因此相等。即使是单节点树，比较步骤仍会执行，但结果表明当前节点自身就是最小子树的根节点，因此返回`(当前节点, 1)`。

选择高度较大的子树的根节点作为返回的节点是因为，最深的节点（即最大深度的叶子节点）位于这棵更高的子树中。因此，包含所有最深节点的最小子树必然也在这个更高的子树中。返回较高子树的根节点确保了返回的子树包含了所有最深的叶子节点，这是解题核心所在。

在算法中，对于空节点，递归函数`traverse`会返回`(None, 0)`。这里返回的高度0表示当前节点不存在任何子树，即没有高度。该值用于递归过程中比较节点的高度，以确定哪个子树是更高的，或者在两个子树高度相等时确认叶节点的高度。这种处理方式使得算法能够正确处理没有子节点的情况，同时简化了代码的复杂性，因为不需要编写额外的逻辑来专门处理空节点。