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

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