网站设计一个月多少钱,中国著名外贸公司有哪些,互联网公司加盟,二手域名购买已备案124. 二叉树中的最大路径和
问题#xff1a;
二叉树中的 路径 被定义为一条节点序列#xff0c;序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点#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解决
这道题典型的dfs问题我们只需要dfs拿到子树可以提供的最大价值就好对于这种规模不同的相同子问题直接dfs递归走起。
所以我们的dfs在计算的时候
一方面要统计该子树所拥有的的最大路径和用来和最终结果做比较一方面要计算该子树可以提供给父亲的最大价值从而递归
func maxPathSum(root *TreeNode) int {maxNum : math.MinInt32 //这里不要用Int因为Int为0如果给个用例是负数就过不了了得给它来个大负数var dfs func(root *TreeNode) intdfs func(root *TreeNode) int {if root nil {return 0}left : dfs(root.Left)right : dfs(root.Right)innerMaxNum : left root.Val right //当前子树最大路径和所以下面需要和外面的maxNum做对比maxNum max(innerMaxNum, maxNum)outMaxNum : root.Val max(left, right) //当前子树可以提供给父亲节点最大价值用于递归延续return max(outMaxNum, 0)}dfs(root)return maxNum
}func max(a, b int) int {if a b {return a}return b
}
