leetcode 刷題之路 63 Binary Tree Zigzag Level Order Traversal

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]
]      

題目要求，按照zigzag的順序通路樹。這道題算是樹的層序周遊的一個變種。

回想之前寫樹的層序周遊時，利用隊列來輔助操作，通路目前節點的同時，将樹的左右孩子push到隊列當中，這樣當上一次節點通路完成後，下一層節點已經全部按照順序加入到了隊列當中。若要以zigzag的形式通路，當上一層通路完成後，下一層的節點要逆序通路。要達到這個目的，我們自然而然會想到先進後出的棧，通路上一層節點時将其左右孩子入棧，然後再按照出棧的順序通路下一層節點，得到的順序正好和上一次節點通路順序相反。當然，一個棧是不夠用的，否則孩子節點壓入棧後，覆寫了尚未通路的上一層節點，就成了樹的先序周遊了。

程式中使用兩個棧s1，s2來輔助操作，s1中儲存奇數層（從1開始計算）的節點，奇數層的周遊順序是從左到右，是以節點應該以從右向左的順序壓入棧s1中，s2中儲存偶數層（從1開始計算）的節點，偶數層的周遊順序是從右向左，是以節點應該以從左到右的順序壓入棧s2中，展現在程式上，就是節點右孩子先于左孩子壓入棧s1中，節點左孩子先于右孩子壓入棧s2中，隻要初始順序正确，下面s1，s2來回倒騰，順序是定死的。

AC code：

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int> > zigzagLevelOrder(TreeNode *root) 
    {
        vector<int> temp;
        vector<vector<int>> ret;
        if(root==NULL)
            return ret;
        stack<TreeNode*> s1,s2;
        s1.push(root);
        while(!s1.empty()||!s2.empty())
        {
            if(!s1.empty())
            {
                temp.clear();
                while(!s1.empty())
                {
                    root=s1.top();
                    temp.push_back(root->val);
                    if(root->left!=NULL)
                        s2.push(root->left);
                    if(root->right!=NULL)
                        s2.push(root->right);
                    s1.pop();
                }
                ret.push_back(temp);
            }
            if(!s2.empty())
            {
                temp.clear();
                while(!s2.empty())
                {
                    root=s2.top();
                    temp.push_back(root->val);
                    if(root->right!=NULL)
                        s1.push(root->right);
                    if(root->left!=NULL)
                        s1.push(root->left);
                    s2.pop();
                }
                ret.push_back(temp);
            }
        }
    }
};