给定一个节点,刻录整个二叉树需要多长时间？

Question

我在一次模拟采访中遇到了一个问题,我必须找到一个二进制树在一个给定节点已经着火后完全烧毁多久.

"从一个叶子节点开始刻录二进制树.从一个节点到另一个节点刻录的时间是多少？整个树被烧毁的时间是什么？火将从一个节点传播到所有路径. "

假设你有一棵这样的树,其中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

在了解了一点之后,我做了一个小小的研究,想弄清楚如何去做.我找到了这篇很酷的文章并跟进了它并实现了背后的想法.

我的方法是找到直径,以及树的高度,以寻找节点的最远节点.但是,当我实现我的函数时,我只是将起始节点的结果发送到给定节点的末尾而不检查先前的父节点.这是我在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(从给定节点的0开始).但同样,我没有得到树的全部范围.根据我自己的理解,它必须适用于所有情况.那么,什么搜索在这里有用,DFS还是BFS？我认为考虑到这一点将指导我走向我的解决方案,但又一次.任何反馈意见:)

Answer 1

对于那些想知道这篇文章发生了什么的人，使用的解决方案是这样的：

LeafSide = []

class Node:
    """Tree class."""

    def __init__(self, key):
        """Declare values of a node."""
        self.left = None
        self.right = None
        self.value = key


def leafHeight(root, leaf):
    """Height of the leaf."""
    if root is None:
        return 0
    else:
        if root.left is leaf:
            aux = 1 + leafHeight(root.right, leaf)
            LeafSide.append(aux)
            return 1
        if root.right is leaf:
            aux = 1 + leafHeight(root.left, leaf)
            LeafSide.append(aux)
            return 1
        return 1 + max(leafHeight(root.left, leaf), leafHeight(root.right, leaf))


def timeBurn(root, leaf):
    """How long will it take to burn the the node to furthest node."""
    hl = leafHeight(root.left, leaf)
    hr = leafHeight(root.right, leaf)
    opposite_LeafSide = 1 + hl + hr
    return max(opposite_LeafSide, LeafSide[0])


if __name__ == '__main__':
    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" % (timeBurn(root, root.left.right)))

时间：O(n)

空间：O(n)

如果您注意到，每个节点的值为 1。节点的值对于此问题并不重要。它只是代表了其中的一些价值。我拥有一个的原因是考虑第二个（1秒节点）。感谢所有帮助过我的人。我很喜欢阅读你们谈论的所有评论和方法:)。如果您对如何改进代码有更好的想法，请随时在下面发表评论！