我是从
https://leetcode.com/discuss/37282/simple-python-recursive-solution-bfs-o-n-80ms
这就是答案
给定一棵二叉树,求其最小深度。
最小深度是从

节点向下到最近的叶节点。

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)将被解包,而node 2将被完全忽略因此,如果节点2没有子节点,而节点3有子节点,那么在随后的迭代中使用节点3是不是错了?

最佳答案

你遗漏的一点是

nodes.pop(0)

弹出第0个元素。
所以你错了:
由于堆栈只弹出列表的最后一个元素,所以。。。
想象一棵二叉树:
            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/

10-12 07:38