《剑指offer刷题笔记》31、不分行从上往下打印二叉树【c++详细题解】

太过爱你忘了你带给我的痛 2021-07-24 19:38 256阅读 0赞

### **题目** ###

从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。

**样例**

输入如下图所示二叉树[8, 12, 2, null, null, 6, null, 4, null, null, null]
        8
       / \
      12  2
         /
        6
       /
      4
    
    输出：[8, 12, 2, 6, 4]

### **思路** ###

**(BFS)**  O ( n ) O(n) O(n)  
我们从根节点开始按宽度优先的顺序遍历整棵树，每次先扩展左儿子，再扩展右儿子。

这样我们会：

1.  先扩展根节点；
2.  再依次扩展根节点的左右儿子，也就是从左到右扩展第二层节点；
3.  再依次从左到右扩展第三层节点；
4.  依次类推

所以BFS的顺序就是这道题目要求的顺序。

**时间复杂度**

BFS时每个节点仅被遍历一次，所以时间复杂度是  O ( n ) O(n) O(n)。

### **代码** ###

/** * 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<int> printFromTopToBottom(TreeNode* root) { 
            vector<int>res;
            if(!root) return res;
            queue<TreeNode*>q;
            q.push(root);
            while(!q.empty())
            { 
                auto t = q.front();
                res.push_back(t->val);
                q.pop();
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            return res;
        }
    };