V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Elethom
V2EX  ›  算法

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

  •  
  •   Elethom · 2019-02-20 15:19:31 +08:00 · 2722 次点击
    这是一个创建于 1864 天前的主题,其中的信息可能已经有所发展或是发生改变。

    刚才面试的时候遇到的题。思路大概是用 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
        1
    sigmapi  
       2019-02-20 16:24:08 +08:00   ❤️ 1
    用 max, max2 分别记录最大值和次大值,遍历树,更新 max 和 max2
    最后返回 max + max2
    aijam
        2
    aijam  
       2019-02-20 16:30:39 +08:00   ❤️ 1
    其实就是找出最大的两个数相加,和 array 里找最大两个数的差别就是遍历方式不同而已。
    rayingecho
        3
    rayingecho  
       2019-02-20 16:41:04 +08:00   ❤️ 1
    rayingecho
        4
    rayingecho  
       2019-02-20 16:43:54 +08:00   ❤️ 1
    楼主你的算法思路是没问题的, 但是有很多的重复计算, 加上一个 cache 缓存已经计算过的值就可以了
    当然也可以像我在 #3 贴的那样换成 bottom-up dp, 不需要额外空间
    Elethom
        5
    Elethom  
    OP
       2019-02-20 16:50:58 +08:00
    谢谢各位。

    @rayingecho
    发现了,把重复的计算去掉就好了。不用 cache,计算的时候直接比较就行。
    MinakoKojima
        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)
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2866 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 33ms · UTC 11:37 · PVG 19:37 · LAX 04:37 · JFK 07:37
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.