首页 > 代码库 > [LeetCode] Binary Tree Maximum Path Sum（最大路径和）
[LeetCode] 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 / 2 3Return
6.
题目意思很简单，就是给定一棵二叉树，求最大路径和。path 可以从任意 node 开始，到任意 node 结束。
这道题在 LeetCode 上的通过率只有 20% 多一点，并被标记为 Hard ，但实际上这是一道相当好的问题，在北美的 CS 求职面试中也是一道高频题，下文我将尝试用最容易理解的方式去分析这道题目。
我的思路
1. 我们直接从题目的问题来分析。给定一棵二叉树，我们怎么来求其最大路径和呢？稍做思考，不难得到以下结论：
当前二叉树的双路
最大路径和 = max(左子树的双路最大路径和, 右子树的双路最大路径和, 当前二叉树在包含根结点情况下的双路最大路径和);
2. 很显然，要解决上面的问题，关键在于怎么求二叉树在包含根结点情况下的双路最大路径和，而要求二叉树在包含根结点情况下的双路最大路径和，首先得先求二叉树的单路最大路径和，请看以下分析：
当前二叉树的单路
最大路径和 = max(左子树的单路最大路径和 + 根结点值, 右子树的单路最大路径和 + 根结点值, 根结点值);
当前二叉树在包含根结点情况下的双路
最大路径和 = 左子树的单路最大路径和 + 根结点值 + 右子树的单路最大路径和;
3. 通过 1 和 2，我们很容易发现，该题可以采用分治法来解决，实际上，与二叉树有关的绝大多数问题，我们都可以采用分治的思想。通常，分治法避免使用全局变量，因此我将会封装一个 returnType 类型，来作为返回值，如下：
struct returnType{ returnType(const int maxSinglePathSum, const int maxDoublePathSum) : maxSinglePathSum_(maxBranch), maxDoublePathSum_(maxSum) { } int maxSinglePathSum_; int maxDoublePathSum_;};
4. 可以 AC 的完整源代码如下：
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ struct returnType{ returnType(const int maxSinglePathSum, const int maxDoublePathSum) : maxSinglePathSum_(maxSinglePathSum), maxDoublePathSum_(maxDoublePathSum) { } int maxSinglePathSum_; int maxDoublePathSum_;};class Solution {public:
int maxPathSum(TreeNode *root) { return maxPathRec(root).maxDoublePathSum_; } returnType maxPathRec(TreeNode *root) { if (root == NULL) { return returnType(0, numeric_limits<int>::min()); } // Devide returnType left = maxPathRec(root->left); returnType right = maxPathRec(root->right); // Conquer int subMaxSinglePathSum = max(left.maxSinglePathSum_, right.maxSinglePathSum_); int maxSinglePathSum = root->val; maxSinglePathSum = max(subMaxSinglePathSum + maxSinglePathSum, maxSinglePathSum); int subMaxDoublePathSum = max(left.maxDoublePathSum_, right.maxDoublePathSum_); int maxDoublePathSum = max(maxSinglePathSum, left.maxSinglePathSum_ + root->val + right.maxSinglePathSum_); maxDoublePathSum = max(subMaxDoublePathSum, maxDoublePathSum); return returnType(maxSinglePathSum, maxDoublePathSum); }};
[LeetCode] Binary Tree Maximum Path Sum（最大路径和）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。