博文中会简要介绍Leetcode P0124题目分析及解题思路。
“Binary Tree Maximum Path Sum”这道题是一道比较难的题目，这道题其实运用了bottom-up的动态规划思想，但是由于给定的是树结构，很难直接自下而上地进行动态规划，所以仍需要使用深度优先搜索，这里采用递归回溯的方法来解题。
Given a non-empty 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. Example 1:
Input: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7 Output: 42
这里我们依旧采用递推表达式的方式来解释递归回溯的返回值，也就是每一层应当从下层获取到什么。
对于任意一个结点n来说，我们令其左子树是left，右子树是right，那么其实对于这个结点而言，有四种可能的路径，
1. dfs(left)+dfs(right)+n.val,
此时结点n是路径中的一点，非路径两端，那么最长路径就是左右子树的最长路径的和，再加上当前结点n的值。
2. dfs(left)+n.val
此时结点n作为左子树路径延伸出来的终点。
3. dfs(right)+n.val
同理上述，结点n是右子树路径延伸出来的终点
4. n.val
结点n本身是路径起点
返回值是上述2、3和4中的最大值，而全局最值则是1、2、3和4中的最大值。
以下是Java的题解代码实现。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxPathSum(TreeNode root) {
if (root == null)
return 0;
this.dfs(root);
return this.maxSum;
}
private int maxSum = Integer.MIN_VALUE;
private int dfs(TreeNode curr) {
if (curr.left == null && curr.right == null) {
this.maxSum = Math.max(this.maxSum, curr.val);
return curr.val;
}
int leftPathSum = curr.val, rightPathSum = curr.val;
if (curr.left != null)
leftPathSum += this.dfs(curr.left);
if (curr.right != null)
rightPathSum += this.dfs(curr.right);
int pathSum = leftPathSum+rightPathSum-curr.val;
int localMax = max(curr.val, leftPathSum, rightPathSum);
this.maxSum = max(maxSum, pathSum, localMax);
return localMax;
}
private int max(int... nums) {
int max = Integer.MIN_VALUE;
for (int num: nums) {
max = Math.max(max, num);
}
return max;
}
}
以下是C++的题解代码实现。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxPathSum(TreeNode* root) {
if (!root)
return 0;
this->Dfs(root);
return _max_path;
}
private:
int _max_path = INT_MIN;
int Dfs(TreeNode *curr) {
if (!curr->left && !curr->right) {
_max_path = max(_max_path, curr->val);
return curr->val;
}
int left_path = curr->val, right_path = curr->val;
if (curr->left)
left_path += this->Dfs(curr->left);
if (curr->right)
right_path += this->Dfs(curr->right);
int path_sum = left_path+right_path-curr->val;
int local_max = this->Max({curr->val, left_path, right_path});
_max_path = this->Max({_max_path, local_max, path_sum});
return local_max;
}
int Max(initializer_list<int> args) {
int maximum = *(args.begin());
for (int num: args)
maximum = max(maximum, num);
return maximum;
}
};