给定一个具有-ve和+ve值的二叉树。打印所有从根到任意节点的路径,其中max sum.do it in 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[]时,如果path已打印
问题:这会多次打印一些路径。此外,面试官想要一次遍历。这需要2。1才能找到最大和。其他到打印路径。
发布于 2013-01-19 17:42:51
在树上执行深度优先搜索,计算所有子路径的总和,并将其存储在包含等长子路径的有序列表数组中。很容易看出,这可以在O(n)中完成,只需遍历图形一次。
结果是一个数组a,其中a[i]包含长度为i的路径列表。保留最大索引j的记录,并最终打印列表a[j]中的所有路径。
https://stackoverflow.com/questions/14412990
复制相似问题