递归二叉树最大路径的呼叫解释总和

给定一个二叉树，找到最大路径总和。

对于这个问题，路径被定义为从一些起始节点到沿着父子连接的树中的任何节点的任何节点序列。路径必须包含至少一个节点，并且不需要来通过根。

例如：考虑到以下二叉树，
1 
/\ 
2 3 
返回6.

此问题的递归解决方案是这样的：

int max = Integer.MIN_VALUE; 

public int maxPathSum(TreeNode root) { 
    helper(root); 
    return max; 
} 

private int helper(TreeNode root) { 
    if (root == null) return 0; 
    int left = Math.max(helper(root.left), 0); 
    int right = Math.max(helper(root.right), 0); 
    max = Math.max(max, root.val + left + right); 
    return root.val + Math.max(left, right); 
}

我们呼吁helper为离开孩子，并检查离开的孩子是否大于零。

然后我们称helper为正确的孩子，并检查正确的孩子是否大于零。

然后我们检查当前的max值与总和root.val + left + right - 这也很清楚。

但是，在回报声明中，我们只有根值和其中一个孩子的总和。为什么我们只有一个孩子在这里，但如果他们都是积极的，他们不是两个？

来源

2017-08-25 rset_d

递归方法不返回解决方案本身，它只返回该部分的最大值。最终的解决方案是在最大变量中计算的。

如果您检查maxPathSum方法，它返回的最大值不是从辅助方法返回的值。

这是因为可能的是，该解决方案不接触根，如这里：

来源

2017-08-25 08:04:46 Selindek

在辅助方法有一个赋值'最大= Math.max（最大值，root.val +左+右）;' - 这很清楚。但为什么我们返回'root.val + Math.max（左，右）;'？总结'root.val'的目的是什么，这会如何影响'max'变量的值？ –

辅助方法返回给定子树的最大非完整路径。最大变量包含'已完成'路径 - 开始并结束于给定的子树中。因此，当辅助方法返回时，它返回一个可能的半路径，可以从另一个分支开始与另一半结合起来，并且如果这两个半部分的组合值大于实际最大值，那么它将是新的最大值。 – Selindek

递归二叉树最大路径的呼叫解释总和

回答

相关问题