当前位置: 代码迷 >> 数据结构与算法 >> 二叉树求结点之和最大的路径,该如何解决
  详细解决方案

二叉树求结点之和最大的路径,该如何解决

热度:313   发布时间:2016-05-23 09:15:14.0
二叉树求结点之和最大的路径
一个二叉树,结点的类型是
struct   NODE{
int   data;
NODE   *lchild,*rchild;
};
创建完树之后要求一条所有的data之和最大的路径该怎么做呢?

------解决方案--------------------
根据递归式啊!

以S为根的树的最大路径==max{ 以SR为根的树的最大路径, 以SL为根的树的最大路径 } + S.data

比较浪费的办法是:对每个节点,均设置一个保存以该节点为根的最大路径的数组。



------解决方案--------------------
一个前序遍历的问题
calculate()
{
更新节点之和
if(当前节点是叶子节点)
判断是否已经达到最大
否则
{
if(当前节点有左子树)
递归左子树
if(当前节点有右子树)
递归右子树
}
}
------解决方案--------------------
这样不就得了:
初始设置跟节点为最大值的节点,然后遍历这棵树,找到最大和的结点,然后再从此结点往上找,不就找到路径了嘛
------解决方案--------------------
to medie2005(阿诺):
只要注意到:

以S为根的树的最大路径==max{ 以SR为根的树的最大路径, 以SL为根的树的最大路径 } + S.data
--------------------------------------------------
根据你的方法,我想是得不到最大的路径和。如果某个节点的两孩子的值比其他任何节点的值都大很多很多,且在遍历的时候你只能取其中一个孩子的值,这样就不能得到最大的路径和。。。
  相关解决方案
本站暂不开放注册!
内测阶段只得通过邀请码进行注册!
 
  • 最近登录:Sat Oct 21 14:50:33 CST 2017
  • 最近登录:Sat Oct 21 14:50:33 CST 2017
  • 最近登录:Sat Oct 21 14:50:33 CST 2017
  • 最近登录:Sat Oct 21 14:50:33 CST 2017
  • 最近登录:Sat Oct 21 14:50:33 CST 2017