查找树中相同值节点的最大连通区域大小的算法

Question

这是我在面试中遇到的一个问题，我仍然不确定如何解决它。

假设我们有一棵数字树，我们想要找到树中节点具有相同值的最大连通区域的大小。例如，在这棵树中

    3
   /  \
  3    3
 / \  / \
1   2 3  4

答案是 4，因为你有一个由 4 个相连的 3 组成的区域。

Answer 1

我会建议使用接受两个输入的函数进行深度优先搜索:

1. 目标值
2. 一个起始节点

并返回两个输出:

1. 值为目标值的节点子树的大小
2. 节点子树内最大的连通域

然后您可以使用虚拟目标值(例如 -1)和根节点调用此函数，它将在第二个输出中返回答案。

在伪代码中:

dfs(target_value,start_node):
  if start_node.value == target_value:
     total = 1
     best = 0
     for each child of start_node:
       x,m = dfs(target_value,child)
       best = max(m,best)
       total += x
     return total,best
  else
     x,m = dfs(start_node.value,start_node)
     return 0,max(x,m)

_,ans = dfs(-1, root_node)
print ans