我将尝试解决以下问题,假设我有这棵二叉树...
3
/ \
9 20
/ \
15 7
然后我需要获取每一层的所有节点,这样我的结果就会是...
[[3],[9,20],[15,7]]
我相信我已经接近解决方案,但我不确定哪里出了问题,如果有人能帮我检查我的解决方案那就太好了,如果我走错了路,请告诉我。
我的第一步是使用以下函数获取树的深度...
def get_depth(self, root):
if root.left == None and root.right == None:
return 1
return max(self.get_depth(root.left), self.get_depth(root.right)) + 1
深度为
3
。接下来,我调用了一个函数,旨在给我期望的结果...
def levelOrder(self, root):
depth = self.get_depth(root)
return self.find_comb(root, [[]]*depth, 0)
def find_comb(self, root, result, level):
if root is None:
return None
self.find_comb(root.left, result, level+1)
self.find_comb(root.right, result, level+1)
result[level].append(root.val)
return result
我的想法是,我会通过树进行递归,而“level”参数将跟踪我目前所在的当前级别。然后,我将在该索引处将该级别上的所有“root.val”附加到结果中。例如,假设我位于第1级(我们从0开始),那么第1级上的节点为9和20。因此,结果看起来像“[[], [9, 20],[],[]]”,并且它将针对树的每个级别执行此操作。我希望我的逻辑清晰明了。但是,我得到的结果却是...
[[9, 15, 7, 20, 3], [9, 15, 7, 20, 3], [9, 15, 7, 20, 3]]
result[level].append(root.val)
。例如,如果result=[[]]*3
,那么result[0].append(1)
将会得到[[1], [1], [1]]
。节点出现的顺序可以通过跟踪递归轻松地进行调整。 - Unni