Ex32-II 从上到下打印二叉树II

题目描述

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。 例如: 给定二叉树：[3,9,20,null,null,15,7]， 输出： [ [3], [9,20], [15,7] ]

解题思路

使用两个计数变量：this_level和next_level，表示当前层和下一层的结点的个数。

• 每从queue里面pop出一个元素，this_level减1；
• 每将一个元素push到queue里面，next_level加1；
• 当this_level减为0，把next_level赋值给this_level，然后next_level清0，将一个vec push到vecs里面。

代码

class Solution
{
public:
  std::vector<std::vector<int> >
  levelOrder (TreeNode *root)
  {
    std::vector<std::vector<int> > vecs;
    if (!root)
      return vecs;
    std::queue<TreeNode *> q;
    q.push (root);
    int this_level = 1, next_level = 0;
    std::vector<int> vec;
    while (!q.empty ())
      {
        TreeNode *node = q.front ();
        vec.push_back (node->val);
        q.pop ();
        if (node->left)
          {
            q.push (node->left);
            ++next_level;
          }
        if (node->right)
          {
            q.push (node->right);
            ++next_level;
          }
        --this_level;
        if (this_level == 0)
          {
            vecs.push_back (vec);
            vec.clear ();
            this_level = next_level;
            next_level = 0;
          }
      }
    return vecs;
  }
};

结果

执行结果：通过

执行用时：8 ms, 在所有 C++ 提交中击败了57.47%的用户

内存消耗：12.6 MB, 在所有 C++ 提交中击败了34.85%的用户