二叉树层次遍历求深度
二叉树的深度
http://www.nowcoder.com/questionTerminal/435fb86331474282a3499955f0a41e8b
思路:
·借助队列,对二叉树进行层次遍历
·在层次遍历的过程中,每当队列中某一层的节点出队完成后,高度+1;
·关键点:如何判别某一层的节点出队完成
在出队之前,此时队列中记录的只有某一层节点,所以队列的大小就是某一层节点的个数,当个数减到0时,则说明改层节点全部出队完成。
public int TreeDepth2(TreeNode *pRoot){ if(pRoot==null) return 0;//如果root为空 queue<TreeNode*> q; q.push(pRoot); int level=0,size; while(!q.empty()){//队列非空时继续循环 size=q.size(); while(size--){ auto node = q.front(); q.pop(); if(node->left) q.push(node->left); if(node->right) q.push(node->right); } level ++; } return level; }