求二叉树上任意两个节点之间的最大和，应该怎么优化？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

已注册用户请登录

这是一个创建于 2425 天前的主题，其中的信息可能已经有所发展或是发生改变。

刚才面试的时候遇到的题。思路大概是用 maxTree() 算从 root 开始的最大值，用 maxNodes() 算任意两节点之间的最大值，每个 node 比较 maxNodes(left)、maxNodes(right)、maxTree(left) + maxTree(right) + value 三者之间的最大值，用递归。

 但是感觉每个 node 都要算好几遍，而且还是递归，效率会很低，遇到大一点的要炸。有什么办法可以优化吗？
 代码：
 class TreeNode { var value: Int var left: TreeNode? var right: TreeNode? init(_ value: Int) { self.value = value } } func maxTree(_ root: TreeNode) -> Int { // max from root if root.left == nil && root.right == nil { return root.value } else if root.left == nil { return maxTree(root.right!) + root.value } else if right == nil { return maxTree(root.left!) + root.value } return max(maxTree(root.left!), maxTree(root.right!)) + root.value } func maxNodes(_ root: TreeNode) -> Int { // max between any 2 nodes if root.left == nil && root.right == nil { return root.value } else if root.left == nil { return max(maxNodes(root.right!), root.value + maxTree(root.right!)) } else if root.right == nil { return max(maxNodes(root.left!), root.value + maxTree(root.left!)) } return max(max(maxNodes(root.left!), maxNodes(root.right!)), maxTree(root.left!) + maxTree(root.right!) + root.value) }

  第 1 条附言    2019-02-20 16:49:13 +08:00 
 Solved. 在计算每个节点的最大枝的时候直接进行一次比较就行了。
 class Solution { func maxPathSum(_ root: TreeNode?) -> Int { // max between any 2 nodes var r = 0 func maxTree(_ root: TreeNode?) -> Int { if let node = root { let val = node.val let left = max(0, maxTree(node.left)) let right = max(0, maxTree(node.right)) r = max(r, left + val + right) return val + max(left, right) } return 0 } if let node = root { r = node.val maxTree(root) return r } return 0 } }

  
  
 root
 maxtree
 left
 right
6 条回复    2019-04-18 10:25:26 +08:00 
           1
 
 sigmapi   
   2019-02-20 16:24:08 +08:00    1 
 用 max, max2 分别记录最大值和次大值，遍历树，更新 max 和 max2
最后返回 max + max2
  
 
 
           2
 
 aijam   
   2019-02-20 16:30:39 +08:00    1 
 其实就是找出最大的两个数相加，和 array 里找最大两个数的差别就是遍历方式不同而已。
  
 
 
           3
 
 rayingecho   
   2019-02-20 16:41:04 +08:00    1 
 一次后序遍历就可以了
https://github.com/aylei/leetcode-rust/blob/master/src/n0124_binary_tree_maximum_path_sum.rs
  
 
 
           4
 
 rayingecho   
   2019-02-20 16:43:54 +08:00    1 
 楼主你的算法思路是没问题的, 但是有很多的重复计算, 加上一个 cache 缓存已经计算过的值就可以了
当然也可以像我在 #3 贴的那样换成 bottom-up dp, 不需要额外空间
  
 
 
           5
 
 Elethom   OP
   2019-02-20 16:50:58 +08:00 
 谢谢各位。

@rayingecho 
发现了，把重复的计算去掉就好了。不用 cache，计算的时候直接比较就行。
  
 
 
           6
 
 MinakoKojima   
   2019-04-18 10:25:26 +08:00 
 这个问题是一般树的直径问题的一个特例。从任一点向下 dfs() or bfs() 到距离最远的点 u，再从 u 出发找距离最远的点 v，u 与 v 之间的距离就是直径，这种算法没有递归常数更小。

[证明]( https://blog.csdn.net/su20145104009/article/details/51297098)