AcWing 44. 分行从上往下打印二叉树

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 44. 分行从上往下打印二叉树原题链接中等

作者：

extrovert , 2019-01-11 04:41:54 , 所有人可见 , 阅读 5564

107

33

算法1

(BFS) $O(n)$

在上一道题《不分行从上往下打印二叉树》的基础上修改代码。

区别在于，每一层结束的时候，往queue里塞一个NULL做标记。

在queue里读取一个数出来之后，先看看是不是level标识符NULL(因为是BFS，当前level读完，下一个level有哪些要读的也都放在queue里了，可以在queue结尾给加一个新的NULL), 是的话再看看是不是整个树读完了(即queue里没有点了)。

时间复杂度分析：每个点遍历一次

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> printFromTopToBottom(TreeNode* root) {
        vector<vector<int>> res;
        if(!root) return res;
        queue<TreeNode*> q;
        q.push(root);
        q.push(NULL); //root层的标识符

        vector<int> cur;
        while(q.size()){
            TreeNode* t = q.front();
            q.pop();

            if(t){ //跟上一道题同样的操作
                cur.push_back(t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            else{
                if(q.size()) q.push(NULL); 
                res.push_back(cur); 
                cur.clear();
            }
        }
        return res;

    }
};

14 评论

废物宝宝 2022-08-01 17:56

其实每一次while存的都是一行的结点每次只取该行结点就可以了

class Solution {
public:
    vector<vector<int>> printFromTopToBottom(TreeNode* root) {
        vector<vector<int>>res;
        if(!root)return res;
        queue<TreeNode*> q;
        q.push(root);
        while(q.size()){
            int len=q.size();
            vector<int>row;
            while(len--){
                auto t=q.front();
                q.pop();
                row.push_back(t->val);
                if(t->left)q.push(t->left);
                if(t->right)q.push(t->right);
            }
            res.push_back(row);
        }
        return res;
    }
};

匿迹名称 2023-05-29 18:49

强

czg 2023-06-25 17:30

这个时间复杂也是O(N)吗

王二的门下走狗 2023-04-03 18:05

class Solution {
    vector<vector<int>> ans;
    void dfs(TreeNode* r, int level)
    {
        if(!r) return;
        if(level == ans.size())
            ans.push_back(vector<int>());
        ans[level].push_back(r -> val);
        dfs(r -> left, level + 1);
        dfs(r -> right, level + 1);
    }
public:
    vector<vector<int>> printFromTopToBottom(TreeNode* root) {
        dfs(root, 0);
        return ans;
    }
};

Bingxiu 2023-01-06 16:58

我天，我的代码居然几乎一毛一样！
我的代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> printFromTopToBottom(TreeNode* root) {
        if(root==NULL) return vector<vector<int>>();
        queue<TreeNode*> q;
        vector<vector<int>> r;
        vector<int> s;
        q.push(root),q.push(NULL);
        while(!q.empty()){
            TreeNode* f=q.front();
            q.pop();
            if(f!=NULL){
                s.push_back(f->val);
                if(f->left!=NULL) q.push(f->left);
                if(f->right!=NULL) q.push(f->right);
            }
            else{
                r.push_back(s),s.clear();
                if(!q.empty()) q.push(NULL);
            }
        }
        return r;
    }
};