LeetCode(Binary Tree Level Order Traversal, 2, Zigzag) 두 갈래 나무의 차원을 두루 훑어보다

1, 제목 요구사항:
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example: Given binary tree  {3,9,20,#,#,15,7} ,

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

2. 
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example: Given binary tree  {3,9,20,#,#,15,7} ,

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7]
  [9,20],
  [3],
]

3.
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example: Given binary tree  {3,9,20,#,#,15,7} ,

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

코드:

class Solution {
public:
    vector<vector<int> > ans;
    vector<vector<int> > levelOrder(TreeNode *root) {

        if (NULL == root) {
            return ans;
        }
        vector<TreeNode*> q;
        int next_level_cnt = 1;// 
        int level_start = 0;// o 
        int level_idx = 1;
        q.push_back(root);
        while (level_start < q.size())
        {
            vector<int> level;
            int cur_level_cnt = next_level_cnt;
            int level_end = level_start + cur_level_cnt;// 
            next_level_cnt = 0;
            for (size_t i = level_start; i < level_end; ++i)
            {
                TreeNode* node = q[i];
                level.push_back(node->val);
                
                if(node->left != NULL)
                {
                    q.push_back(node->left);
                    ++next_level_cnt;
                }
                if(node->right != NULL)
                {
                    q.push_back(node->right);
                    ++next_level_cnt;
                }
            }
            ans.push_back(level);
            level_start += cur_level_cnt;// 
        }
        return ans;
    }
    
    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {// 
    
        if (NULL ==  root) {
            return ans;
        }
        stack<TreeNode*> even_st;
        stack<TreeNode*> odd_st;
        int level_idx = 1;
        int next_level_cnt = 1;
        int level_start = 0;
        odd_st.push(root);
        while (!odd_st.empty() || !even_st.empty()) {
            vector<int> level;
//            cout << "odd_st size : " << odd_st.size() << "  even st size : " << even_st.size() << endl;
            if((level_idx & 1) == 1)// , 
            {
                while (!odd_st.empty()) {
                    TreeNode* node = odd_st.top();
                    odd_st.pop();
                    level.push_back(node->val);
                    if(node->left != NULL)
                        even_st.push(node->left);
                    if(node->right != NULL)
                        even_st.push(node->right);
                }
            }
            else// ， ， ， 
            {
                while (!even_st.empty()) {
                    TreeNode* node = even_st.top();
                    even_st.pop();
                    level.push_back(node->val);
                    if(node->right != NULL)
                        odd_st.push(node->right);
                    if(node->left != NULL)
                        odd_st.push(node->left);
                    
                }
            }
            ++level_idx;
            ans.push_back(level);
        }
        return ans;
    }
};