单页网站编辑器,北京招聘网站开发,通州广州网站建设,asp.net开发微网站开发文章目录 零、原题链接一、题目描述二、测试用例三、解题思路四、参考代码 零、原题链接 124. 二叉树中的最大路径和
一、题目描述
二叉树中的 路径 被定义为一条节点序列#xff0c;序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径… 文章目录 零、原题链接一、题目描述二、测试用例三、解题思路四、参考代码 零、原题链接 124. 二叉树中的最大路径和
一、题目描述
二叉树中的 路径 被定义为一条节点序列序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 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三、解题思路
基本思路 初看这一题好像没有思路。但是仔细分析一下其实每个节点无非就三种情况一种是成为路径的根另一种是非根最后一种就是不选如果是路径的根那就要计算其左子树和右子树的路径和如果是非根那就选择左右子树最大的一个成为路径的一部分如果左右子树本身都是负的那就不选了这个节点。 个人建议当碰到无法无从下手的题目可以从细节考虑分析可能发生的情况然后每种情况要怎么处理。具体思路 如果节点为空则返回 0 计算左右子树最大路径如果选取该节点为根则更新最大值如果不选该节点为根则返回左右子树最大路径如果为负则返回 0
四、参考代码
时间复杂度 O ( n ) \Omicron(n) O(n)【n 为节点数】 空间复杂度 O ( n ) \Omicron(n) O(n)
/*** 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 ans -1000;int maxPathSum(TreeNode* root) {maxPath(root);return ans;}int maxPath(TreeNode* root) {if (!root)return 0;int l, r;l maxPath(root-left);r maxPath(root-right);// 选取该节点为根ans max(ans, l r root-val);// 不选return max(0, max(l, r) root-val);}
};
