我看到这段代码来自 https://leetcode.com/discuss/37282/simple-python-recursive-solution-bfs-o-n-80ms
这就是
的答案Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root
node down to the nearest leaf node.
class Solution:
# @param {TreeNode} root
# @return {integer}
def minDepth(self, root):
if not root:
return 0
nodes = [(root, 1)]
while nodes:
node, curDepth = nodes.pop(0)
if node.left is None and node.right is None:
return curDepth
if node.left:
nodes.append((node.left, curDepth + 1))
if node.right:
nodes.append((node.right, curDepth + 1))
所以我的困惑是,假设节点 1 将节点 2 和节点 3 作为其 .left 和 .right 子节点,那么堆栈将是 [(node 2, someDepth), (node 3 someDepth)]。然后,由于堆栈只会弹出列表的最后一个元素,因此 (node 3 someDepth) 将被解包,而节点 2 则被完全忽略。那么,如果节点 2 没有子节点,而节点 3 有子节点,那么在后续迭代中使用节点 3 是否是错误的?
最佳答案
你错过的一点是
nodes.pop(0)
弹出第 0 个元素。
所以你错了:
Then as the stack would only pop out the last element of the list, then...
想象一棵二叉树:
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \ /
8 9 10 11 12
这里状态空间将更改为(为简单起见,节点被命名为其内容编号):
# Before 1st iteration.
nodes = [(1, 1)]
# 1st iteration.
node, curDepth = 1, 1
nodes = [(2, 2), (3, 2)]
# 2nd iteration.
node, curDepth = 2, 2
nodes = [(3, 2), (4, 3), (5, 3)]
# 3rd iteration.
node, curDepth = 3, 2
nodes = [(4, 3), (5, 3), (6, 3), (7, 3)]
# 4th iteration.
node, curDepth = 4, 3
nodes = [(5, 3), (6, 3), (7, 3), (8, 4), (9, 4)]
# 5th iteration.
node, curDepth = 5, 3
# Here if node.left is None and node.right is None becomes True and curDepth i.e. 3 is returned.
可以看出,节点是按(树的)广度进行处理的,因此它是一个 BFS。
关于python - 该代码如何找到二叉树的最小深度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30570720/