1.题目描写
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.
2.解决方案1
class Solution {
public:
int maxDepth(TreeNode *root) {
if(root == NULL){
return 0;
}
deque<TreeNode*> deqNodes;
deqNodes.push_back(root);
int depth = 0;
int alreadyDoneCount = 1;
while(deqNodes.empty() == false){
TreeNode* lastNode = deqNodes.back();
deqNodes.pop_back();
alreadyDoneCount--;
if(lastNode->left){
deqNodes.push_front(lastNode->left);
}
if(lastNode->right){
deqNodes.push_front(lastNode->right);
}
if(alreadyDoneCount == 0){
++depth;
alreadyDoneCount = deqNodes.size();
}
}
return depth;
}
};
思路：采取宽度优先搜索，
只有当添加的全处理了，树的深度才增加1，这个是个小技能。
3.解决方案2
class Solution {
public:
int maxDepth(TreeNode *root) {
if(root == NULL ){
return 0;
}else if(root != NULL && (root->left == NULL && root->right == NULL)){
return 1;
}
int leftTreeDepth = maxDepth(root->left);
int rightTreeDepth = maxDepth(root->right);
int maxDepth = leftTreeDepth > rightTreeDepth ? leftTreeDepth : rightTreeDepth;
return maxDepth + 1;
}
};
思路：树的遍历固然可以用递归，但会比较慢。
http://www.waitingfy.com/archives/1586