一, 题目说明
题目 104. Maximum Depth of Binary Tree, 求二叉树的最大高度. 难度是 Easy!
二, 我的解答
按层遍历二叉树, 就可以计算最大深度. 下面是非递归算法:
- class Solution{
- public:
- int maxDepth(TreeNode* root){
- queue<TreeNode*> q;
- TreeNode* p;
- if(root==NULL) return 0;
- q.push(root);
- int maxDep = 0;
- int curLevelNum = 1,nextLevelNum = 0;
- while(! q.empty()){
- for(int i=0;i<curLevelNum;i++){
- p = q.front();
- q.pop();
- if(p->left !=NULL){
- q.push(p->left);
- nextLevelNum++;
- }
- if(p->right !=NULL){
- q.push(p->right);
- nextLevelNum++;
- }
- }
- curLevelNum = nextLevelNum;
- nextLevelNum = 0;
- maxDep++;
- }
- return maxDep;
- }
- };
性能如下:
- Runtime: 8 ms, faster than 89.13% of C++ online submissions for Maximum Depth of Binary Tree.
- Memory Usage: 19.3 MB, Less than 79.12% of C++ online submissions for Maximum Depth of Binary Tree.
三, 优化措施
Easy, 就不优化了.
来源: http://www.bubuko.com/infodetail-3446338.html