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

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=root->val;
int ans = findMaxSum(root,m,maxNode);
if(ans==0) return maxNode;
return ans;
}
};
Binary Tree Zigzag Level Order Traversal

[cpp] class Solution {
public:
vector > zigzagLevelOrder(TreeNode *root) {
vector> ans;
if(root==NULL) return ans;
queue q;
q.push(root);
TreeNode* pre = root;
vector nowVec;
ans.push_back(nowVec);
while(!q.empty()){
TreeNode* tmp = q.front();
q.pop();
ans[ans.size()-1].push_back(tmp->val);
if(tmp->left!=NULL) q.push(tmp->left);
if(tmp->right!=NULL) q.push(tmp->right);
if(tmp==pre){
ans.push_back(nowVec);
if(!q.empty())
pre = q.back();
}
}
ans.pop_back();
for(int i=1;i for(int j=0,k=ans[i].size()-1;j std::swap(ans[i][j++],ans[i][k--]);
return ans;
}
};