【题目】
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
.
【分析】
需要考虑以上两种情况:
1 左子树或者右子树中存有最大路径和 不能和根节点形成一个路径
2 左子树 右子树 和根节点形成最大路径
【代码】
/*********************************
* 日期:2014-12-23
* 作者:SJF0115
* 题号: Binary Tree Maximum Path Sum
* 来源:https://oj.leetcode.com/problems/binary-tree-maximum-path-sum/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int maxPathSum(TreeNode *root) {
if(root == NULL){
return 0;
}//if
maxSum = INT_MIN;
maxPath(root);
return maxSum;
}
private:
int maxSum;
int maxPath(TreeNode *node){
if(node == NULL){
return 0;
}//if
// 左子树最大路径值(路径特点:左右节点只能选一个)
int leftMax = maxPath(node->left);
// 右子树最大路径值(路径特点:左右节点只能选一个)
int rightMax = maxPath(node->right);
// 以node节点的双侧路径((node节点以及左右子树))
int curMax = node->val;
if(leftMax > 0){
curMax += leftMax;
}//if
if(rightMax > 0){
curMax += rightMax;
}//if
maxSum = max(curMax,maxSum);
// 以node节点的单侧路径(node节点以及左右子树的一个)
if(max(leftMax,rightMax) > 0){
return max(leftMax,rightMax) + node->val;
}
else{
return node->val;
}
}
};
//按先序序列创建二叉树
int CreateBTree(TreeNode*& T){
int data;
//按先序次序输入二叉树中结点的值,-1表示空树
cin>>data;
if(data == -1){
T = NULL;
}
else{
T = (TreeNode*)malloc(sizeof(TreeNode));
//生成根结点
T->val = data;
//构造左子树
CreateBTree(T->left);
//构造右子树
CreateBTree(T->right);
}
return 0;
}
int main() {
Solution solution;
TreeNode* root(0);
CreateBTree(root);
cout<<solution.maxPathSum(root);
}
分享到:
相关推荐
主要介绍了LeetCode -- Path Sum III分析及实现方法的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下
leetcode的题目:Balanced Binary Tree
双指针算法,python数组双指针算法求和问题LeetCode2sum3sum4sum含代码
文档python数组双指针算法求和问题LeetCode2sum3sum4sum含代码提取方式是百度网盘分享地址
答案LeetCode_1_TwoSum LeetCode 问题:给定一个整数数组,找出两个数字,使它们相加为特定的目标数字。 函数 twoSum 应该返回两个数字的索引,使它们相加为目标,其中 index1 必须小于 index2。 请注意,您返回的...
二叉树前序遍历,leetcode
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 ...
BinaryTree.py是一个方便的工具,它可以构建和显示编码时所需的二叉树 演示 您需要在使用之前导入该类 import BinaryTree as bt 从值/对象列表或二叉树构造二叉树 t1 = bt.BinaryTree([1,2,3,4,5,'#',6,7,'#','#','#...
144.Binary_Tree_Preorder_Traversal二叉树的前序遍历【LeetCode单题讲解系列】
145.Binary_Tree_Postorder_Traversal二叉树的后序遍历【LeetCode单题讲解系列】
Source file for LeetCode Permutations Problem
94.Binary_Tree_Inorder_Traversal二叉树的中序遍历【LeetCode单题讲解系列】
我的个人微信公众号:Microstrong 微信公众号ID:MicrostrongAI 微信公众号介绍:Microstrong(小强)同学主要研究机器学习、深度学习、计算机视觉、智能对话系统相关内容,分享在学习过程中的...102. Binary Tree Leve
leetcode 树节点二叉树最大路径和 执行 : /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val ...
Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum. Note: A leaf is a node with no children. Example: Given the below binary tree and sum = 22, ...
LeetCode — Path Sum III分析及实现方法 题目描述: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need...
leetcode-tag-Tree
Leetcode-tree 94题 Binary Tree Inorder Traversal 对于树的问题,大多数我们都会使用递归的方法。原因是树的左子树也是树,右子树也是树,使用递归的方法最简单快捷。这道题是需要我们用Inorder的顺序输出节点。in...
144-Binary Tree Preorder Traversal94-Binary Tree Inorder Traversal145-Binary Tree Postorder Traversal(后续的非递归时间不够可以先跳过,有点难)层次遍历,队列辅助,相当于广搜。102-Binary Tree Level ...
* [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]...