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

题目描述

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。 例如: 给定二叉树: [3,9,20,null,null,15,7], 返回其层次遍历结果： [ [3], [20,9], [15,7] ]

解题思路

这道题需要两个辅助的stack：

• 当遍历方式应为正序时，下一层的存储应为先压入左子树，然后再压入右子树；这样的话，就可以先弹出右子树，再弹出左子树；这就保证了下一层的的遍历为倒序；
• 当遍历方式应为倒序时，下一层的存储应为先压入右子树，然后再压入左子树；这样的话，就可以先弹出左子树，再弹出右子树；这就保证了下一层的的遍历为正序。

代码

class Solution
{
public:
  std::vector<std::vector<int> >
  levelOrder (TreeNode *root)
  {
    std::vector<std::vector<int> > vecs;
    if (!root)
      return vecs;
    std::vector<std::stack<TreeNode *> > stacks (2);
    int index = 0;
    stacks[index].push (root);
    std::vector<int> vec;
    while (!stacks[index].empty ())
      {
        TreeNode *node = stacks[index].top ();
        vec.push_back (node->val);
        stacks[index].pop ();
        if (index)
          {
            if (node->right)
              stacks[1 - index].push (node->right);
            if (node->left)
              stacks[1 - index].push (node->left);
          }
        else
          {
            if (node->left)
              stacks[1 - index].push (node->left);
            if (node->right)
              stacks[1 - index].push (node->right);
          }
        if (stacks[index].empty ())
          {
            index = 1 - index;
            vecs.push_back (vec);
            vec.clear ();
          }
      }
    return vecs;
  }
};

结果

执行结果：通过

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

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