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

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