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

V2EX = way to explore

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

现在注册

已注册用户请登录

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

刚才面试的时候遇到的题。思路大概是用 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
    }
}

6 条回复 • 2019-04-18 10:25:26 +08:00

sigmapi

2019-02-20 16:24:08 +08:00

用 max, max2 分别记录最大值和次大值，遍历树，更新 max 和 max2
最后返回 max + max2

aijam

2019-02-20 16:30:39 +08:00

其实就是找出最大的两个数相加，和 array 里找最大两个数的差别就是遍历方式不同而已。

rayingecho

2019-02-20 16:41:04 +08:00

一次后序遍历就可以了
https://github.com/aylei/leetcode-rust/blob/master/src/n0124_binary_tree_maximum_path_sum.rs

rayingecho

2019-02-20 16:43:54 +08:00

楼主你的算法思路是没问题的, 但是有很多的重复计算, 加上一个 cache 缓存已经计算过的值就可以了
当然也可以像我在 #3 贴的那样换成 bottom-up dp, 不需要额外空间

Elethom

2019-02-20 16:50:58 +08:00

谢谢各位。

@rayingecho
发现了，把重复的计算去掉就好了。不用 cache，计算的时候直接比较就行。

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)