python-3.x - 给定一个节点，烧毁整个二叉树需要多长时间？

Question

我在一次模拟面试中遇到了一个问题，我必须找出在一个给定节点已经着火后，二叉树会完全烧毁多长时间。

"A binary tree is started burning from a leaf node. What is the time(1second to burn from node to node) it takes to entire tree get burned? The fire will spread to all the paths from a node."

假设您有一棵这样的树，其中 N 是着火的节点。这是 发生在第一秒，其中秒是 s，所以在第 0 秒:

           1
       /       \
      1          1
    /  \          \
   1    1          1
      /   \         \
     1     N         1
                      \
                       1

一秒钟过去后，树将更新为更多被销毁的节点。 下一秒 (s + 1) 的示例将是这样的:

           1
       /       \
      1          1
    /  \          \
   1    N          1
      /   \         \
     1     N         1
                      \
                       1

下一秒(s + 2)的例子是这样的:

           1
       /       \
      N          1
    /  \          \
   1    N          1
      /   \         \
     N     N         1
                      \
                       1  

现在在第三秒 (s + 3) 将是这样的:

           N
       /       \
      N          1
    /  \          \
   N    N          1
      /   \         \
     N     N         1
                      \
                       1

同样的模式，树会在(s + 7)后被烧毁

           N
       /       \
      N          N
    /  \          \
   N    N          N
      /   \         \
     N     N         N
                      \
                       N

在了解了一点之后，我做了一个小的研究来弄清楚如何去做。我发现这很酷 article并跟进并实现背后的想法。

我的方法是找出树的直径和高度，以寻找最远的节点到节点。但是，当我实现我的功能时，我只得到从起始节点到给定节点结束的结果，而没有检查之前的父节点。这是我在 Python 3 中的实现:

# Tree class
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.value = key

# Maximum height of a tree
def maxHeight(root):
    if root is None:
        return 0
    else:
        return 1 + max(maxHeight(root.left), maxHeight(root.right))

# Diameter of the tree
def maxDiameter(root):
    how_long = 0
    if root is None:
        return 0
    else:
        root_diameter = maxHeight(root.left) + maxHeight(root.right)

        left_diameter = maxDiameter(root.left)
        right_diameter = maxDiameter(root.right)
        how_long = max(max(left_diameter, right_diameter), root_diameter)
        return how_long

# Sample code
root = Node(1)
root.left = Node(1)
root.right = Node(1)
root.left.left = Node(1)
root.left.right = Node(1)
root.left.right.left = Node(1)
root.left.right.right = Node(1)
root.right.right = Node(1)
root.right.right.right = Node(1)
root.right.right.right.right = Node(1)
print ("Starting from the given node, it will take %ds to burn the whole tree" % (maxDiameter(root.left.right)))

此示例的预期输出应为 6s(从给定节点的 0s 开始)。但同样，我没有得到树的全部范围。根据我自己的理解，它必须适用于所有情况。那么，什么搜索在这里会有帮助，DFS 或 高炉？我认为牢记这一点将再次引导我找到解决方案。感谢任何反馈:)

Answer 1

我突然想到您需要以下内容:

1. 起始节点是在根的左边还是右边。
2. 起始节点的深度(称之为dStart)。
3. 在起始节点的分支上离根最远的节点的深度(即根的左侧或右侧)。我们称之为 dSameSide
4. 起始节点和#3 中标识的节点的最低共同祖先的深度。 (称之为 dCommonAncestor)
5. 树对面最低节点的深度，dOppositeSide。

您可以从树的单次中序遍历中获取所有这些信息。

从起始节点到树那一侧最深节点所需的步数是(dSameSide - dCommonAncestor) + (dStart - dCommonAncestor)。

从起始节点到对面最深节点的步数为(dStart + dOppositeSide)。

燃烧整棵树所需的步数是这两者中的最大值。

我会把实现留给你。你可能会发现 How to find the lowest common ancestor of two nodes in any binary tree?有帮助。