美文网首页
[LeetCode] 103. Binary Tree Zigz

[LeetCode] 103. Binary Tree Zigz

作者: 弱花 | 来源:发表于2018-11-02 11:18 被阅读0次

    原题链接

    题目要求以“Z”字型遍历二叉树,并存储在二维数组里。

    思路:
    利用BFS,对每一层进行遍历。对于每一层是从左还是从右,用一个整数型判断当前是偶数行还是奇数行就可以了。

    class Solution
    {
    public:
      vector<vector<int>> res;
      vector<vector<int>> zigzagLevelOrder(TreeNode *root)
      {
        if (root == NULL)
          return res;
        stack<TreeNode *> sta;
        sta.push(root);
        TravelNextLevel(sta, 1);
        return res;
      }
    
    private:
      void TravelNextLevel(stack<TreeNode *> &sta, int level)
      {
        res.emplace_back();
        res.back().reserve(sta.size());
        stack<TreeNode *> nextSta;
        while (!sta.empty())
        {
          TreeNode *curNode = sta.top();
          sta.pop();
          res.back().push_back(curNode->val);
          if (level % 2 != 0)
          {
            if (curNode->left)
              nextSta.push(curNode->left);
            if (curNode->right)
              nextSta.push(curNode->right);
          }
    
          if (level % 2 == 0)
          {
            if (curNode->right)
              nextSta.push(curNode->right);
            if (curNode->left)
              nextSta.push(curNode->left);
          }
        }
    
        if (!nextSta.empty())
          TravelNextLevel(nextSta, level + 1);
      }
    };
    

    相关文章

      网友评论

          本文标题:[LeetCode] 103. Binary Tree Zigz

          本文链接:https://www.haomeiwen.com/subject/fovqxqtx.html