LeetCode Maximum Depth of Binary Tree
来源：程序员人生 发布时间：2015-04-11 09:44:36 阅读次数：2404次
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
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
