刚才面试的时候遇到的题。思路大概是用 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)
}
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
}
}
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
|
4
rayingecho 2019-02-20 16:43:54 +08:00 1
楼主你的算法思路是没问题的, 但是有很多的重复计算, 加上一个 cache 缓存已经计算过的值就可以了
当然也可以像我在 #3 贴的那样换成 bottom-up dp, 不需要额外空间 |
5
Elethom OP |
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) |