问题描述:
Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.
For example:
Given the below binary tree,
1 / \ 2 3
Return 6
.
原问题链接:https://leetcode.com/problems/binary-tree-maximum-path-sum/
问题分析
这个问题一开始比较难找到解决的思路。因为这里要求的路径并不一定是从树的根节点经过的路径。而如果把这个问题更加一般化的话,我们计算从某个节点到叶节点的所有可能最大路径,无非就是递归的计算它的两个子节点的最大路径值,再把它们的值和自身加起来。只是我们最终返回的那个是经过根节点的值,它不一定是最大的。
在这里,突然给了我们一个想法,就是在前面递归的过程中,每次都要比较和计算一个当前节点的最大路径值。而如果在这个时候我们用一个全局的变量保存这个最大值,每次都和这个值比较调整的话,这个问题就可以解决了。
于是我们有如下的代码:
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { int maxValue; public int maxPathSum(TreeNode root) { maxValue = Integer.MIN_VALUE; maxPathDown(root); return maxValue; } private int maxPathDown(TreeNode node) { if(node == null) return 0; int left = Math.max(0, maxPathDown(node.left)); int right = Math.max(0, maxPathDown(node.right)); maxValue = Math.max(maxValue, left + right + node.val); return Math.max(left, right) + node.val; } }
从实现的思路来说,这里通过借求经过根节点的所有路径的最大值,在每次递归的过程中比较计算最长的路径。这种方式比较巧妙。
相关推荐
leetcode的题目:Balanced Binary Tree
java lru leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 ...LeetCode ...Maximum Subarray 55 Jump Game 56 Merge Intervals 64 Minimum Path Sum 73
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
leetcode leetcode练习 twosum 问题 ;add two numbers问题;reverse integer问题;最大不重复子字符串长度问题;atoi问题;
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
LeetCode: ://leetcode.com/ 程式语言:C ++ # 标题 解决方案 困难 1个 简单的 2个 中等的 3 中等的 4 难的 5 中等的 6 中等的 7 反整数 7反向整数 简单的 8 字符串到整数(atoi) 8字符串到整数(atoi) ...
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
Maximum XOR of Two Numbers in an Array leetcode-1707. Maximum XOR With an Element From ArraysubSequence问题一般可以用DP解决,复杂度为O(N ^ 2) subArray问题一般可以使用滑动窗口方法(或以DP结尾,在...
Leetcode:Leetcode提交
LeetCode 101:和你一起你轻松刷题(C++)
binary_tree_paths.py: bst_search.py: find_disappeared_numbers.py: frequecy_sort.py: height_checker.py: Jewels_and_stones.py: last_stone_weight.py: Linked_list_cycle.py: long_pressed_name.py...
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
leetcode:leetcode刷题
leetcode卡 LeetCode 记录一下再LeetCode上刷的题,坚持每天刷一道吧 2017.06.12 打卡[LeetCode 2. Add Two Numbers], Linked list 2017.06.13 打卡[LeetCode 200. Number of Islands], BFS 2017.06.14 打卡...
Leetcode\TwoSum\TwoSum.cs 问题: 业绩报告: 反转整数 代码: Leetcode\ReverseInteger\ReverseInteger.cs 问题: 业绩报告: 回文数 代码: Leetcode\PalindromeNumber\PalindromeNumber.cs 问题: 从排序数组中...