难度: Medium
Submission
运行时间: 27 ms
内存: 15.9 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 __init__(self):
self.res = []
def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
self.maxDepth(root)
return self.res
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
# 当前节点距离叶子节点的高度（最大深度）
h = max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
if len(self.res) < h:
self.res.append([])
self.res[h - 1].append(root.val)
return h
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 __init__(self):
self.res = [] # 用于存储结果的列表
def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
self.maxDepth(root) # 调用 maxDepth 函数遍历二叉树
return self.res
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
# 递归计算左右子树的最大深度
left_depth = self.maxDepth(root.left)
right_depth = self.maxDepth(root.right)
# 当前节点距离叶子节点的高度（最大深度）
h = max(left_depth, right_depth) + 1
# 如果 self.res 的长度小于 h，则添加一个新的列表
if len(self.res) < h:
self.res.append([])
# 将当前节点的值添加到对应高度的列表中
self.res[h - 1].append(root.val)
return h # 返回当前节点的高度
Explore
在这个算法中，所有叶子节点被分类到最底层的列表中是通过递归函数`maxDepth`的返回值来确保的。叶子节点是没有左子树和右子树的节点，所以对于叶子节点，`maxDepth`返回的是1（`max(0, 0) + 1`）。这意味着叶子节点总是被放在`self.res[0]`的位置，即最底层的列表中。因为他们的高度`h`被计算为1，使用`h-1`作为索引时正好指向列表的第一个位置。
当一个节点只有左子树或只有右子树时，`maxDepth`函数会递归地调用存在的子树并计算其深度，而另一个为`None`的子树的深度会返回0。例如，如果只有左子树，`left_depth`将是该左子树的最大深度，而`right_depth`将是0。然后，当前节点的高度计算为`max(left_depth, right_depth) + 1`，即仅考虑存在的子树的深度加1。这样可以正确地评估出从当前节点到叶节点的最大深度。
在这个算法中，`self.res`列表的索引是通过节点的高度`h`来确定的，其中`h`是当前节点到叶节点的最大深度。由于列表索引是从0开始的，而高度是从1开始的，因此使用`h-1`作为索引来对应高度`h`的节点。这样，高度为1的节点（叶子节点）就存储在索引0的位置，高度为2的节点存储在索引1的位置，以此类推。
在添加新列表到`self.res`时，检查`len(self.res) < h`是为了确保在尝试将节点值添加到`self.res[h-1]`时该索引已经存在。这防止了索引错误。如果当前节点的高度`h`大于`self.res`的当前长度，说明我们还没有为这个高度创建存储节点的列表，因此需要添加新的空列表。在正常运行的递归过程中，`self.res`的长度不可能大于`h`，因为`h`是从根节点向下递增的，而每次遇到新的高度才会添加新的列表。