leetcode代码分类汇总之-树 (二)

[cpp] public:
vector > levelOrder(TreeNode *root) {
TreeNode* pre_level = root;
vector> result;
if(!root) return result;
queue q;
q.push(root);
result.push_back(vector());
while(!q.empty()){
TreeNode* node = q.front();
q.pop();
result.back().push_back(node->val);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
if(pre_level==node){
pre_level = q.back();
result.push_back(vector());
}
}
result.pop_back();
return result;
}
};

public:
vector > levelOrder(TreeNode *root) {
TreeNode* pre_level = root;
vector> result;
if(!root) return result;
queue q;
q.push(root);
result.push_back(vector());
while(!q.empty()){
TreeNode* node = q.front();
q.pop();
result.back().push_back(node->val);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
if(pre_level==node){
pre_level = q.back();
result.push_back(vector());
}
}
result.pop_back();
return result;
}
};
Binary Tree Level Order Traversal II

[cpp] class Solution {
public:
void RecBottom(TreeNode* root,vector>& result,int level){
if(!root) return;
result[result.size()-1-level].push_back(root->val);
RecBottom(root->left,result,level+1);
RecBottom(root->right,result,level+1);
}
int MaxHeight(TreeNode* root,int d){
if(!root) return d;
return max(MaxHeight(root->left,d+1),MaxHeight(root->right,d+1));
}
vector > levelOrderBottom(TreeNode *root) {
int height = MaxHeight(root,0);
vector> result(height);
RecBottom(root,result,0);
return result;
}
};

class Solution {
public:
void RecBottom(TreeNode* root,vector>& result,int level){
if(!root) return;
result[result.size()-1-level].push_back(root->val);
RecBottom(root->left,result,level+1);
RecBottom(root->right,result,level+1);
}
int MaxHeight(TreeNode* root,int d){
if(!root) return d;
return max(MaxHeight(root->left,d+1),MaxHeight(root->right,d+1));
}
vector > levelOrderBottom(TreeNode *root) {
int height = MaxHeight(root,0);
vector> result(height);
RecBottom(root,result,0);
return result;
}
};
Binary Tree Maximum Path Sum

[cpp] class Solution {
public:
int findMaxSum(TreeNode* root,int& pathMax,int& maxNode){
if(root==NULL){
pathMax = 0;
return 0;
}
if(root->val>maxNode) maxNode = root->val;
int left,right,leftPath,rightPath;
left = findMaxSum(root->left,leftPath,maxNode);
right = findMaxSum(root->right,rightPath,maxNode);
pathMax = max(max(leftPath,rightPath)+root->val,0);
return max(max(left,right),leftPath+rightPath+root->val);
}
int maxPathSum(TreeNode *root) {
if(root==NULL) return 0;
int m,maxNode