树中具有颜色条件的最长路径

Question

我使用“天真的”解决方案成功解决了这个问题，检查每个节点的最长路径，包括该节点，但被告知有更好的解决方案。

我正在寻求有关如何有效解决此问题以及如何解决类似问题的帮助（将不胜感激提示或思维方法）

假设我有一棵树，其中每个节点都是橙色或白色的。我需要编写一个算法来获取最长“好”路径的长度

“好”路径是指从白色节点开始，向上爬 0 个或更多白色节点，然后向下走 0 个或更多橙色节点的路径

以下一棵树为例

算法应该 return 4 因为最长的路径从 18 开始到 15

Answer 1

你可以用线性时间复杂度来做到这一点：

以post顺序（深度优先）遍历树，对于每个访问过的节点，收集从该节点开始向下的最长单色路径的大小——因此该路径中的所有节点都应该具有与当前节点相同的颜色。我们称这个长度为节点的“单色高度”

此外，如果当前节点为白色，则获取其橙色子节点中最大的单色高度。如果当前（白色）单色高度与橙色高度的总和大于目前的最大值，则保留该总和作为最大化解决方案（目前最佳）。

下面是 Python 中实现该想法的一些代码：

class Node:
    def __init__(self, data, colored=False, left=None, right=None):
        self.data = data
        self.colored = colored
        self.left = left
        self.right = right

def longestpath(root):
    maxlen = 0

    def monochromeheight(node):  # recursive function
        nonlocal maxlen  # this is the overall best result

        if node is None:  # base case
            return 0

        # First get the children's data
        leftheight = monochromeheight(node.left)
        rightheight = monochromeheight(node.right)

        # Then determine the monochrome height of this node
        currheight = 0
        if leftheight > 0 and node.left.colored == node.colored:
            currheight = leftheight
        if rightheight > currheight and node.right.colored == node.colored:
            currheight = rightheight
        currheight += 1

        # Check whether this is a white node with an orange child.
        #   If so, check if the white + orange path form a better solution
        if not node.colored:
            if  node.left and node.left.colored and currheight + leftheight > maxlen:
                maxlen = currheight + leftheight
            if node.right and node.right.colored and currheight + rightheight > maxlen:
                maxlen = currheight + rightheight

        return currheight

    monochromeheight(root)  # ignore returned value
    return maxlen

然后是示例树上的演示运行：

# Demo run on example tree
tree =  Node(20, False,
            Node(18, False,
                Node(32, True,
                    Node(70, False,
                        Node(80, False,
                        )
                    ),
                    Node(13, True,
                        Node(17, True)
                    )
                ),
                Node(22, True)
            ),
            Node(26, True,
                None,
                Node(15, True,
                    Node(30, False,
                        Node(40, False),
                        Node(25, True)
                    ),
                    Node(19, False)
                )
            )
        )

print(longestpath(tree))  # 4

树中具有颜色条件的最长路径

Longest path with color condition in tree

algorithm

tree

binary-tree

graph

graph-algorithm