algorithm - 树中总和最大的路径

Question

给定具有 -ve 和 +ve 值的二叉树。将所有路径的根节点打印到具有最大总和的任何节点。在 O(n) 中执行。只有一次遍历树。

努力:) 1) http://www.geeksforgeeks.org/find-the-maximum-sum-path-in-a-binary-tree/ 是完全不同的问题。

2) O(n) + O(n) 不被接受。

我的做法。

1)

i) 找到可能的最大总和。ii) 遍历保持当前路径和总和的前序。if(curr_sum == max_sum) 打印路径。

2) i) 找到可能的最大总和。ii) 遍历保持当前路径和总和的前序。if(curr_sum == max_sum) 打印路径。还将该节点的地址保存在节点数组 Arr 中。下次当 curr_sum==max_sum 时，如果路径已经打印，只需检查 Arr[]

问题：这将多次打印一些路径。面试官想要一次遍历。这需要 2. 一个来找到 max sum 。其他打印路径。

Answer 1

在树上进行深度优先搜索，计算所有子路径的总和，并将它们存储在包含等长子路径的列表的排序数组中。很容易看出，这可以在 O(n) 中完成，只遍历图一次。

结果是一个数组a，其中a[i]包含长度为路径的列表i。记录最大索引j并最终打印列表中的所有路径a[j]。