首页 > 其他 > 详细

二叉树层序遍历

时间:2021-01-13 23:53:25      阅读:1      评论:0      收藏:0      [点我收藏+]

1. 思路

没啥思路,就是一个宽度优先搜索,一层一层搜即可。
bfs 主要是利用队列来做。
先把root 放到队列中,然后进循环。
每次循环把当前队列的所有元素取出来,加到当前层,然后将他们的左子树,右子树加到队列中去,当前层计算完了以后加到res 里面去。用c++写起来很简洁,个人感觉比java简洁一些。

2. code

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root== nullptr){
            return res;
        }
        queue<TreeNode*> q;
        // 放入队列
        q.push(root);
        while (!q.empty()){
//            auto f = q.front();
//            q.pop();
            // 层次遍历
            vector<int> level;
            int curSize = q.size();
            for (int i = 0; i < curSize; ++i) {
                auto t = q.front();
                q.pop();
                level.push_back(t->val);
                if (t->left){
                    q.push(t->left);
                }
                if (t->right){
                    q.push(t->right);
                }
            }
            res.push_back(level);
        }
        return res;

    }
};

3. 小总结

c++的语法有点奇怪,

// 这样是不行的
queue<*TreeNode>
// 必须写出
queue<TreeNode*> ,

队列存放TreeNode指针。我一开始是写成queue 结构体,也是可以pass,但是耗时4ms,比java的慢,我想不科学啊,c++比java慢? 后面改成存放指针就超过100%了,算是一个比较简单的bfs ,
技术分享图片

技术分享图片

还有一个坑点是 每次循环的时候需要把queue.size赋给一个遍历,因为循环里面会进行pop操作,这样size就会变化。

二叉树层序遍历

原文:https://www.cnblogs.com/gqdw/p/14274658.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号