1、Maximum Depth of Binary Tree
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
class Solution {
public:
int maxDepth(TreeNode *root) {
inMax = 0;
int depth = 0;
if(root){
maxDepth(root,depth);
}
return inMax;
}
void maxDepth(TreeNode* root, int depth){
++depth;
if(!root->left && !root->right){
if(depth >inMax){
inMax = depth;
}
}
if(root->left){
maxDepth(root->left,depth);
}
if(root->right){
maxDepth(root->right,depth);
}
}
int inMax;
};
2、Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes‘ values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ 9 20
/ 15 7
return its zigzag level order traversal as:
[ [3], [20,9], [15,7] ]
分析：有栈来保存结点，第一次先放左孩子后放右孩子，第二次先放右孩子再放左孩子。
class Solution {
public:
vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
vector<vector<int> > result;
stack<TreeNode*> stackNode;
stack<TreeNode*> newStackNode;
vector<int> nodeVec;
if(root){
stackNode.push(root);
while(!stackNode.empty()){
nodeVec.clear();
while(!stackNode.empty()){
TreeNode* node = stackNode.top();
stackNode.pop();
nodeVec.push_back(node->val);
if(node->left){
newStackNode.push(node->left);
}
if(node->right){
newStackNode.push(node->right);
}
}
result.push_back(nodeVec);
nodeVec.clear();
while(!newStackNode.empty()){
TreeNode* node = newStackNode.top();
newStackNode.pop();
nodeVec.push_back(node->val);
if(node->right){
stackNode.push(node->right);
}
if(node->left){
stackNode.push(node->left);
}
}
if(!nodeVec.empty()){
result.push_back(nodeVec);
}
}
}
return result;
}
};
leetcode -day24 Maximum Depth of Binary Tree & Binary Tree Zigzag Level Order Traversal
原文：http://blog.csdn.net/kuaile123/article/details/27683297