二叉树最大路径和中的递归调用解释

Question

这就是问题所在：

给定一棵二叉树，求最大路径和。

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

例如：给定下面的二叉树，

   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);
}

我们为左子调用< code>helper,并检查左子是否大于零。

然后，我们为右孩子调用< code>helper,并检查右孩子是否大于零。

然后我们检查当前的max值和root.val左右-这也很清楚。

但是，在返回语句中，我们只有根值和其中一个子值的和。如果两个孩子都是阳性的，为什么我们只带一个孩子而不带两个？

Answer 1

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

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

这是因为解决方案可能没有触及根，就像下面这样：

       0
     /   \
    1     0
   / \   / \
  2   3 0   0