如何找到bst中任意两个节点之间的最大路径和？
how to find maximum path sum between any two nodes in a bst?
我们如何找到二叉搜索树中任意两个元素之间的最大可能路径和？
我不只是在谈论任何两个叶节点。这个问题包括所有节点。
路径总和是指路径中所有数据元素的总和。
使用伪代码：
Set maxSum = MINVALUE
TreeMaxSum (tree)
maxLeft = TreeMaxSum(tree->left)
maxRight = TreeMaxSum(tree->right)
maxSum = max(maxSum, maxLeft+maxRight+tree->value)
return max(maxLeft, maxRight) + tree->value
TreeMaxSum(tree)
当然，您需要处理常见的边缘情况和 "empty leaf" 值...
我们如何找到二叉搜索树中任意两个元素之间的最大可能路径和？ 我不只是在谈论任何两个叶节点。这个问题包括所有节点。 路径总和是指路径中所有数据元素的总和。
使用伪代码：
Set maxSum = MINVALUE
TreeMaxSum (tree)
maxLeft = TreeMaxSum(tree->left)
maxRight = TreeMaxSum(tree->right)
maxSum = max(maxSum, maxLeft+maxRight+tree->value)
return max(maxLeft, maxRight) + tree->value
TreeMaxSum(tree)
当然，您需要处理常见的边缘情况和 "empty leaf" 值...