求二叉树的高度(非递归)

非递归就是在层次遍历的基础上加上个depth,len变量来记录即可,有点类似于bfs

用c++实现如下:

---

 

 

 1 int treedepth(treenode* proot)
 2     {
 3      queue<treenode*> q;
 4         if(!proot) return 0;
 5         q.push(proot);
 6         int depth=0;
 7         while(!q.empty()){
 8             int len=q.size();//队列的当前大小
 9            　depth++;
10             while(len--){ //循环完就是一层都退出队列了
11                 treenode* temp=q.front();//表头
12                 q.pop();
13                 if(temp->left) q.push(temp->left);
14                 if(temp->right) q.push(temp->right);
15             }
16         }
17         return level;
18     }