LeetCode 热题 100_二叉树中的最大路径和（50_124_困难_C++）(二叉树；深度 ...

题目描述：

二叉树中的 路径 被界说为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定颠末根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
输入输出样例：

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
提示：
树中节点数目范围是 [1, 3 * 104]
-1000 <= Node.val <= 1000
题解：

解题思路：

思路一（深度优先搜索）：

1、盘算一个结点向下的最大路径和，就是盘算左右子树的最大路径相加，再加上本结点的值（当然左右子树最大路径为负数时无需加左右子树）。为了举行上述的盘算，我们需要从递归返回时举行操纵，即从叶结点开始向上盘算，这样我们就能方便的得到每个结点左右子树的最大路径和，进而得到当前结点的最大路径和。在这个过程中采用一个全局变量存储树中的最大路径和。
例： 假设一个结点为root，左子树的最大路径和为leftSum，右子树的最大路径和为rightSum。
则当前结点的最大路径和为（root->val+leftSum+rightSum）这里leftSum和rightSum均大于等于0。
递归返回时我们需要返回：当前结点的值root->val+max（leftSum，rightSum）。这里leftSum和rightSum均大于等于0。（由于我们返回的是一条一直向下的路径）
2、复杂度分析：
① 时间复杂度：O(n)，n代表二叉树中的结点数，需要遍历整个二叉树一次。
② 空间复杂度：O(n)，n代表二叉树中的结点数，最坏环境下递归函数栈的深度是n。
代码实现

代码实现（思路一（深度优先搜索））：

1. class Solution
2. {
3. private:
4.     //maxSum存储二叉树的最大路径
5.     int maxSum=INT32_MIN;
6.    
7.     //递归的求解最大路径
8.     int dfs(TreeNode *root){
9.         if (root==nullptr) return 0;
11.         //左子树向下的路径最大值
12.         int leftSum=max(dfs(root->left),0) ;
13.         //右子树向下的路径最大值
14.         int rightSum=max(dfs(root->right),0);
16.         //当前结点最大路径和
17.         int currentSum=root->val+leftSum+rightSum;
18.         //更新最大路径和
19.         maxSum=max(currentSum,maxSum);
21.         //返回当前结点左右子树中较大的路径
22.         return root->val+max(leftSum,rightSum);      
24.     }
26. public:
27.     //计算一个结点向下的最大路径，就是计算左右子树的最大路径相加再加上本结点
28.     //如果左右子树的最大路径为<0则不进行累加
29.     int maxPathSum(TreeNode *root){
30.         dfs(root);
31.         return maxSum;
32.     }
33. };

复制代码

以思路一为例举行调试

1. #include<iostream>#include <vector>#include <queue>using namespace std;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) {}};//通过数组创建二叉树，-1代表nullptrTreeNode *createTree(const vector<int> &nums){    if (nums.empty()) return nullptr;    queue<TreeNode *> Q;    TreeNode *root=new TreeNode(nums[0]);    Q.push(root);    int i=1;    while (i<nums.size())    {        TreeNode *node=Q.front();        Q.pop();        if (nums[i]!=-1 )        {            node->left=new TreeNode(nums[i]);        }        ++i;        if (nums[i]!=-1 && i<nums.size())        {            node->right=new TreeNode(nums[i]);        }        ++i;    }    return root;    }//中序遍历输出二叉树，验证二叉树创建是否正确void inorder(TreeNode *root){    if(root==nullptr) return;    inorder(root->left);    cout<<root->val<<" ";    inorder(root->right);}class Solution
2. {
3. private:
4.     //maxSum存储二叉树的最大路径
5.     int maxSum=INT32_MIN;
6.    
7.     //递归的求解最大路径
8.     int dfs(TreeNode *root){
9.         if (root==nullptr) return 0;
11.         //左子树向下的路径最大值
12.         int leftSum=max(dfs(root->left),0) ;
13.         //右子树向下的路径最大值
14.         int rightSum=max(dfs(root->right),0);
16.         //当前结点最大路径和
17.         int currentSum=root->val+leftSum+rightSum;
18.         //更新最大路径和
19.         maxSum=max(currentSum,maxSum);
21.         //返回当前结点左右子树中较大的路径
22.         return root->val+max(leftSum,rightSum);      
24.     }
26. public:
27.     //计算一个结点向下的最大路径，就是计算左右子树的最大路径相加再加上本结点
28.     //如果左右子树的最大路径为<0则不进行累加
29.     int maxPathSum(TreeNode *root){
30.         dfs(root);
31.         return maxSum;
32.     }
33. };
34. int main(int argc, char const *argv[]){    vector<int> nums={1,2,3};    //通过数组创建二叉树，-1代表nullptr    TreeNode *root= createTree(nums);        //中序遍历验证二叉树创建是否正确    // inorder(root);    //盘算二叉树中最大路径和并输出    Solution s;    cout<<s.maxPathSum(root);    return 0;}

复制代码

LeetCode 热题 100_二叉树中的最大路径和（50_124)原题链接
欢迎大家和我沟通交换(✿◠‿◠)

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。