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
Return6
.
之前觉得这个是难得一塌糊涂的题目,为五星级难度。
但是自从熟悉了递归回溯,树的遍历,二分法这些相关的算法之后,重新思考一下这道题目。
觉得难度也不过如此,重新评为3到4星级吧。
关键点:
1 每个节点的左右子树都必须保留可以连接的值,本程序作为返回值保留,如节点是root,可以连接的值为root->val, root->val+left_sum, 或者root->val+right_sum;三个值中的最大值。其中left_sum和right_sum分别为左右子树的最大可连接值。
2 额外使用一个全局变量res保留查找到的最大值,遍历完毕这个res就为结果最终最大值。
说的有点绕口,简单来说就是:
注意区分和保存最终最大值和最大可连接值。
//2014-2-17 update
int maxPathSum(TreeNode *root)
{
int res = INT_MIN;
pathSum(root, res);
return res;
}
int pathSum(TreeNode *r, int &res)
{
if (!r) return INT_MIN;
int lsum = pathSum(r->left, res);
int sum = lsum>0? lsum+r->val:r->val;
int rsum = pathSum(r->right, res);
if (rsum > 0) sum += rsum;
res = max(res, max(sum, max(lsum, rsum)));
int t = max(lsum, rsum);
if (t > 0) return r->val+t;
return r->val;
}
顺便说一句,leetcode上的程序和大多博客的程序都有一个bug,就是当空树的时候返回为0,其实应该返回为INT_MIN;
因为如果当所有的节点都为负数的时候,那么最终结果就为0,而不是其中最大的负数。
当然,面试的时候,这个问题是可以问清楚的,看看出题者的原意是什么,看看实际需要是什么,再处理。
分享到:
相关推荐
Binary Tree Maximum Path Sum Populating Next Right Pointers in Each Node Sum Root to Leaf Numbers LCA of Binary Tree 线段树 Range Sum Query - Mutable 排序 插入排序 Insertion Sort List 归并排序 Merge ...
binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { *...
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 ...
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...
104.maximum-depth-of-binary-tree (二叉树的最大深度) 105.construct-binary-tree-from-preorder-and-inorder-traversal (从前序与中序遍历序列构造二叉树) 106.construct-binary-tree-from-inorder-and-postorder-...
* [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]...
Path Sum 2017/03/09 70.Climbing Stairs, 198.House Robber, 55.Jump Game 72.Edit Distance, 97.Interleaving String, 115.Distinct Subsequences 2017/04/24 (Lintcode)92.Backpack, (Lintcode)125.Backpack II, ...
12.2 Querying a binary search tree 289 12.3 Insertion and deletion 294 12.4 Randomly built binary search trees 299 13 Red-Black Trees 308 13.1 Properties of red-black trees 308 13.2 Rotations 312 13.3...
12.2 Querying a binary search tree 289 12.3 Insertion and deletion 294 ? 12.4 Randomly built binary search trees 299 13 Red-Black Trees 308 13.1 Properties of red-black trees 308 13.2 Rotations 312 ...
286 12.2 Querying a binary search tree 289 12.3 Insertion and deletion 294 ? 12.4 Randomly built binary search trees 299 13 Red-Black Trees 308 13.1 Properties of red-black trees 308 13.2 Rotations ...
l2.2 Querying a binary search tree 2S6 l2.3 Insertion and deletion 261 l2.4 Randoinly built binary search trees 265 13 Red-Black Thees 273 l3.l Properties of red-black trees 273 l3.2 Rotations 277 l...
线段树维护区间最大值 Segment-Tree(Maximum) 线段树维护区间最小值 Segment-Tree(Minimum) 线段树维护区间和值 Segment-Tree(Sum) 普通的选择算法 Selection Eratosthenes素数筛法 Sieve-of-Erotosthenes 指针...
12.2 Querying a binary search tree 289 12.3 Insertion and deletion 294 12.4 Randomly built binary search trees 299 13 Red-Black Trees 308 13.1 Properties of red-black trees 308 13.2 Rotations 312 13.3...
1383 Binary Numbers 简单题 1403 Safecracker 简单题 1408 The Fun Number System 简单题 1486 Color the Tree 简单题 1487 Playing Cards 简单题 1489 2^x mod n = 1 简单题,应该有好算法,不过枚举就...
1383 Binary Numbers 简单题 1403 Safecracker 简单题 1408 The Fun Number System 简单题 1486 Color the Tree 简单题 1487 Playing Cards 简单题 1489 2^x mod n = 1 简单题,应该有好算法,不过枚举就...