Binary Tree Maximum Path Sum

描述

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.For example:Given the below binary tree,

  1.   1
  2.  / \
  3. 2   3

Return 6.

分析

这题很难，路径可以从任意节点开始，到任意节点结束。

可以利用“最大连续子序列和”问题的思路，见这节Maximum Subarray。如果说Array只有一个方向的话，那么Binary Tree其实只是左、右两个方向而已，我们需要比较两个方向上的值。

不过，Array可以从头到尾遍历，那么Binary Tree怎么办呢，我们可以采用Binary Tree最常用的dfs来进行遍历。先算出左右子树的结果L和R，如果L大于0，那么对后续结果是有利的，我们加上L，如果R大于0，对后续结果也是有利的，继续加上R。

代码

  1. // Binary Tree Maximum Path Sum
  2. // 时间复杂度O(n)，空间复杂度O(logn)
  3. class Solution {
  4. public:
  5.     int maxPathSum(TreeNode *root) {
  6.         max_sum = INT_MIN;
  7.         dfs(root);
  8.         return max_sum;
  9.     }
  10. private:
  11.     int max_sum;
  12.     int dfs(const TreeNode *root) {
  13.         if (root == nullptr) return 0;
  14.         int l = dfs(root->left);
  15.         int r = dfs(root->right);
  16.         int sum = root->val;
  17.         if (l > 0) sum += l;
  18.         if (r > 0) sum += r;
  19.         max_sum = max(max_sum, sum);
  20.         return max(r, l) > 0 ? max(r, l) + root->val : root->val;
  21.     }
  22. };

注意，最后return的时候，只返回一个方向上的值，为什么？这是因为在递归中，只能向父节点返回，不可能存在L->root->R的路径，只可能是L->root或R->root。

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/binary-tree/recursion/binary-tree-maximum-path-sum.html