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

Question

问题是:

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example: Given the below binary tree,

   1
  / \
 2   3

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

我们为左 child 调用helper 并检查左 child 是否大于零。

然后我们为右 child 调用helper 并检查右 child 是否大于零。

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

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

Answer 1

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

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

这是因为解决方案可能不会触及根，如下所示:

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