首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >树中具有最大和的路径

问树中具有最大和的路径
EN

Stack Overflow用户
提问于 2013-01-19 17:36:59
回答 1查看 3.8K关注 0票数 0

给定一个具有-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才能找到最大和。其他到打印路径。

EN

回答 1

Stack Overflow用户

发布于 2013-01-19 17:42:51

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

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

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/14412990

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档