【剑指Offer】面试题32 - II. 从上到下打印二叉树 II

题目

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

例如:

给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

[

  [3],

  [9,20],

  [15,7]

]

``` 

提示：

节点总数 <= 1000

## 思路

在[【面试题32 - I. 从上到下打印二叉树】](https://www.cnblogs.com/galaxy-hao/p/12369503.html)基础上先计算当前层元素个数，然后依次遍历当前层每个元素，并将其下层节点放入队列中。

### 代码

时间复杂度：O(n)

空间复杂度：O(n)

```cpp

class Solution {

public:

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

        vector<vector<int>> res;

        if (root) {

            queue<TreeNode*> que;

            que.push(root);

            while (!que.empty()) {

                int size = que.size(); //计算一层元素个数

                vector<int> tmp;

                while (size--) {

                    TreeNode *node = que.front();

                    que.pop();

                    tmp.push_back(node->val);

                    if (node->left) que.push(node->left);

                    if (node->right) que.push(node->right);

                }

                res.push_back(tmp);

            }

        }

        return res;

    }

};

巴特西

【剑指Offer】面试题32 - II. 从上到下打印二叉树 II

题目

最新文章

热门文章