`
huntfor
  • 浏览: 201499 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[leetcode]Binary Tree Maximum Path Sum

 
阅读更多

新博文地址:[leetcode]Binary Tree Maximum Path Sum

 

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 3
Return 6.

 这道题是非常好的一道题,树,常规做法是遍历,遍历的做法往往用dfs,代码简单,可读性强。这道题与常规的树的题目不同的一点是,在遍历的过程中,进行了返回处理,而且做法很巧妙。

 

以这棵树为例:

                      2
                   /       \
                1         -1
              /     \     /     \
            1     -3  1       7

 图中红色路径表示的一条最大路径:

先看下递归过程:

以左下角的1为root的树的最大路径肯定是1,而异-3为root的树的最大路径是-3,以他俩的父节点1为根节点的最大路径有这么几种情况:

root.val,  root.val + left , root.val + right ,root.val + left + right

取其中的最大值(图中的例子是root.val + left:2),更新max(上面取四个值得最大值,仅用于更新max)

 

但是这个递归函数的返回不应该包括root.val + left + right,因为黄底色的1作为2的左子树的返回值只能由其他节点经过黄底色的1,传到根节点2,单向,传到2,不能形成折路(谁想到的?太厉害了)

 

好了有了以上的算法思想,代码实现起来就比较容易了:

int max = Integer.MIN_VALUE;
	public int maxPathSum(TreeNode root){
		if(root == null) return 0;
		dfs(root);
		return max;		
	}
	public int dfs(TreeNode root){
		if(root == null) return 0;
		int left = dfs(root.left);
		int right = dfs(root.right);
		int tem = Math.max(root.val, Math.max(left+ root.val, Math.max(right + root.val, root.val + left+ right)));
		max = tem > max ? tem : max;
		return Math.max(root.val, Math.max(root.val + left, root.val + right));
	}
	

 

分享到:
评论

相关推荐

    python-leetcode题解之124-Binary-Tree-Maximum-Path-Sum

    python python_leetcode题解之124_Binary_Tree_Maximum_Path_Sum

    js-leetcode题解之124-binary-tree-maximum-path-sum.js

    javascript js_leetcode题解之124-binary-tree-maximum-path-sum.js

    Leetcode book刷题必备

    31. Binary Tree Maximum Path Sum:二叉树中的最大路径和。 32. Binary Tree Upside Down:将一个二叉树进行翻转。 【位操作】 33. Single Number:找出数组中唯一不出现一次的数字。 34. Single Number II:找出...

    Algorithm-LeetCode-Solution-From-GuaZiDou.zip

    再如,"Binary Tree Maximum Path Sum"问题,要求找到二叉树中从根节点到叶子节点的最大路径和。这个问题可以通过深度优先搜索或广度优先搜索结合动态规划来解决。 GuaZiDou的解决方案不仅包含了代码实现,通常还...

    leetcodetreenode-binary-tree-maximum-path-sum:二叉树最大路径和

    leetcode 树节点二叉树最大路径和 执行 : /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val ...

    Leetcode题目+解析+思路+答案.pdf

    - **Binary Tree Path**:找到二叉树中和为目标值的路径。 - **Sum Root to Leaf Numbers**:计算二叉树所有从根到叶子节点的路径之和。 4. **动态规划(Dynamic Programming)**: - **Best Time To Buy and ...

    LeetCode最全代码

    * [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...

    常见算法题答案及解析

    31. Binary Tree Maximum Path Sum:二叉树中的最大路径和。 32. Binary Tree Upside Down:将二叉树进行上下翻转。 五、位运算 33. Single Number:只出现一次的数字,要求不使用额外空间。 34. Single Number II...

    leetcode答案-leetcode-[removed]用javascript刷LeetCode

    例如,"Binary Tree Maximum Path Sum"(二叉树最大路径和)问题,我们可以使用DFS来计算每个节点到根节点的路径和,然后比较并返回最大值。 在"leetcode-javascript-master"这个压缩包中,很可能包含了作者使用...

    lrucacheleetcode-leetcode:leetcode

    Path to Get All Keys 深度优先搜索 996. Number of Squareful Arrays 拓扑排序 269. Alien Dictionary 单调栈 42. Trapping Rain Water 85. Maximal Rectangle Monotonic stack for 2d array 239. Sliding Window ...

    leetcode答案-LeetCode:LeetCode的回答

    3. "Binary Tree Maximum Path Sum"(二叉树的最大路径和):这是一道困难级别的问题,涉及到深度优先搜索(DFS)和回溯,寻找从根节点到叶子节点的最大路径和。 开源项目“LeetCode-master”很可能包含了这些问题...

    leetcode分类-LeetCode:力码

    Maximum Subarray Minimum Path Sum Unique Paths Unique Paths II Longest Palindromic Substring Interleaving String Triangle Distinct Subsequences Decode Ways Palindrome Partitioning II Maximal Rectangle...

    Leetcode

    还有一些更高级的问题,如 "Binary Tree Maximum Path Sum",它涉及到树的深度优先搜索(DFS)或广度优先搜索(BFS),以及动态规划的策略。这类问题需要理解如何构建和遍历二叉树,并计算路径的最大和。 LeetCode...

    LeetCode:用于测试来自https的问题

    "Binary Tree Maximum Path Sum"则可能涉及到深度优先搜索或广度优先搜索等树遍历策略。 此外,C#的特性如委托、事件、匿名函数、LINQ等也可能在LeetCode的C#解决方案中得到体现。例如,LINQ(Language Integrated ...

    LeetcodeSolutions:我收集的评论很好的leetcode问题解决方案

    而"Binary Tree Maximum Path Sum"(二叉树最大路径和)这类问题则需要结合深度优先搜索来找到最大路径。 在"Merge Intervals"(合并区间)问题中,我们需要对区间进行排序,然后利用双指针技术合并重叠部分,这...

    LeetCode:收集LeetCode问题以使编码面试更加出色!

    另一个例子是“Binary Tree Maximum Path Sum”,需要你找到二叉树中具有最大路径和的路径,这涉及到递归和树的遍历。 解决LeetCode问题的过程中,你还可以学习如何编写清晰、简洁且易于理解的代码,这是面试官非常...

    LeetCode:解决LeetCode的问题

    对于更复杂的题目,如"Binary Tree Maximum Path Sum"(二叉树的最大路径和),我们需要掌握深度优先搜索(DFS)或广度优先搜索(BFS)策略,同时理解和运用树的性质。在这个问题中,我们需要沿着一条路径递归地访问...

    四平方和定理leetcode-leetcode-practice:个人LeetCode练习代码

    104.maximum-depth-of-binary-tree (二叉树的最大深度) 105.construct-binary-tree-from-preorder-and-inorder-traversal (从前序与中序遍历序列构造二叉树) 106.construct-binary-tree-from-inorder-and-postorder-...

    leetcode

    3. "Binary Tree Maximum Path Sum"(二叉树最大路径和):这题需要用到深度优先搜索,同时结合动态规划的思想,寻找一条路径使得经过的所有节点的路径和最大。 五、LeetCode对Java开发者的意义 1. 提升技能:...

Global site tag (gtag.js) - Google Analytics