如何找到二叉树中最长的连续路径

我在采访中被问到这个问题。考虑一个二叉树，我们需要打印的最长路径，其中每个元素相差1如何找到二叉树中最长的连续路径

EG的长度：

回答：5 （4,5,6,7,8 ）

如何做到这一点？我开发了一个算法来打印从根到叶的增长路径，但我并没有开发一个跟踪两个子树上的路径的程序。

编辑：修改后需要找回原始树。

来源

2017-08-13 indian name

修改树并保留它以获取原始树是愚蠢的。相反，通过检查'Math.Abs（node.value - parent.value）> 1'，跳过树差异超过1的那些部分。如果那是真的，沿着这条路走下去没有意义。 – displayName

正如评论

删除所有无效的边缘，我建议由@qwertyman。Ë边缘，其差值大于1
现在我们有了一个林，每个林的计算口径，因为它是在@FilipKočica解给出
答案将是最大直径的所有森林

来源

2017-08-13 18:55:30 marvel308

如何获取原始树 –

只需将无效边存储在数据结构中并稍后将其添加回来 – marvel308

对于每个子树，可以计算从子树根开始的最长递增路径，最长递减路径向下和由子树中任意位置的同一节点向下和向下递增路径组成的最长内部路径。

如果你已经为它的所有孩子拥有了它们，那么很容易计算出它们，所以你可以做它作为任何后序遍历的一部分。

答案是整棵树内最长的内部路径。

来源

2017-08-13 17:54:16

我假设路径必须具有+1的差异并不重要，如示例中所示。相差-1，导致像4 -> 5 -> 4 -> 3 -> 4 -> 5这样的路径也可以。

public int getLongestConsecutivePath(TreeNode root) { 
    return root == null 
     ? 0 
     : getLength(root.left, root.value) + getLength(root.right, root.value); 
} 

private int getLength(TreeNode node, int prevVal) { 
    return node == null || Math.abs(node.value - prevVal) > 1 
     ? 0 
     : Math.max(getLength(node.left, node.value), getLength(node.right, node.value)) + 1; 
}

说明：

如果根本不为空，我们就得到了左，右子树的最大长度，总结它。
为了获得子树中的最大长度，我们递归地获得子树的右侧和左侧子树的最大长度。
- 如果我们已经达到了叶或者如果我们已经达到了一个节点，在中值的差大于1，我们返回0
- 否则，我们从递归左，右子树得到的最大长度，并添加1为了适应这个节点本身。

来源

2017-08-13 18:12:42 displayName

让longest_desc[a]是最长的1×1向下路径从同样longest_asc[a]，下降时间最长的1乘1的增量路径从

下降

对于固定的根R，答案将是longest_desc[R] + longest_asc[R] - 1。

brut force解决方案会从每个节点X执行2次dfs/bfs遍历来计算longest_asc[X] and longest_desc[X]然后将它们合并在一起。由此产生的运行时复杂性将是O(n^2)。

但是我们其实可以做的更好利用动态规划：

longest_asc[X] = max(longest_asc[Y in children[X]] with Y = X + 1) 
longest_desc[X] = max(longest_desc[Y in children[X]] with Y = X - 1)

然后我们就可以计算在一个单一的DFS遍历=>O(n)解决所有的值。

来源

2017-08-15 07:50:40 CodingPill

如何找到二叉树中最长的连续路径

回答

相关问题