二叉树层次遍历求深度

二叉树的深度

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;

}
全部评论

相关推荐

1 收藏 评论
分享
牛客网
牛客企业服务