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

秒速五厘米 2021-07-24 16:01 373阅读 0赞

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

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

**样例**

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

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

**(BFS)** O ( n ) O(n) O(n)  
宽度优先遍历，一层一层来做。即：

1.  将根节点插入队列中；
2.  创建一个新队列，用来按顺序保存下一层的所有子节点；
3.  对于当前队列中的所有节点，按顺序依次将儿子加入新队列，并将当前节点的值记录在答案中；
4.  重复步骤2-3，直到队列为空为止。

**时间复杂度**  
树中每个节点仅会进队出队一次，所以时间复杂度是  O ( n ) O(n) O(n)。

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

/** * 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> get_val(vector<TreeNode*> level)
        { 
            vector<int> res;
            for (auto &u : level)
                res.push_back(u->val);
            return res;
        }
    
        vector<vector<int>> printFromTopToBottom(TreeNode* root) { 
            vector<vector<int>>res;
            if (!root) return res;
            vector<TreeNode*>level;
            level.push_back(root);
            res.push_back(get_val(level));
            while (true)
            { 
                vector<TreeNode*> newLevel;
                for (auto &u : level)
                { 
                    if (u->left) newLevel.push_back(u->left);
                    if (u->right) newLevel.push_back(u->right);
                }
                if (newLevel.size())
                { 
                    res.push_back(get_val(newLevel));
                    level = newLevel;
                }
                else break;
            }
            return res;
        }
    };

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

我们给每一层加一个结尾标记`NULL`,当我们访问到一层的结尾时，由于BFS的特点，我们刚好把下一层都加到了队列中。这个时候就可以给这层加上结尾标记NULL了。

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

vector<vector<int>> printFromTopToBottom(TreeNode* root) {