【LeetCode】 103. Binary Tree Zigzag Level Order Traversal

Description

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).

給一棵二元樹，按照蜿蜒階層順序(zigzag level order)回傳它的每個節點的值。(先從左到右，下一個階層從右到左，以此類推)。

Example:

Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its zigzag level order traversal as:
[
  [3],
  [20,9],
  [15,7]
]

Solution

• 偷懶的方法，去把102. Binary Tree Level Order Traversal的Code先複製過來，得到一般的level order之後，再把奇數階的反轉即可。

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void BFS(vector<vector<int>>& ans,vector<int>& nodes,vector<pair<TreeNode*,int>>& queue,int &level)
    {
        //take new node from queue
        pair<TreeNode*,int> n = queue.front();
        queue.erase(queue.begin());
        if(!n.first)return;
        
        //check level
        if(level==n.second)
            nodes.push_back(n.first->val);
        else
        {
            level = n.second;
            ans.push_back(nodes);
            nodes.clear();
            nodes.push_back(n.first->val);
        }
        //push next node into queue
        queue.push_back(pair<TreeNode*,int>(n.first->left,n.second+1));
        queue.push_back(pair<TreeNode*,int>(n.first->right,n.second+1));
        
        //run until queue is empty
        while(queue.size()!=0)
            BFS(ans,nodes,queue,level);
        
        //check last level is pushed
        if(nodes.size()!=0)
        {
            ans.push_back(nodes);
            nodes.clear();
        }
    }
    
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        vector<int> nodes;
        int level=0;
        vector<pair<TreeNode*,int>> queue(1,pair<TreeNode*,int>(root,0));
        BFS(ans,nodes,queue,level);
        for(int i=0;i<ans.size();i++)
        {
            if(i%2)
                reverse(ans[i].begin(),ans[i].end());
        }
        return ans;
    }
};

tags: LeetCode C++