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

思路：

Binary Tree Level Order Traversal那题的变种。一样的层序访问，区别仅仅在于访问是左向右，右向左交替进行。

1. 用两个stack来存储curLevel和nextLevel的节点可以实现这样的左右顺序反转。因为stack是先进后出的，节点push进stack的顺序和pop出stack的顺序正好是相反的：

假设stack curLevel pop出的第一个节点是该层的最左节点x，压入x->left和x->right进stack nextLevel。这样依次类推，等整个curLevel的节点都pop出来后，x->left和x->right在nextLevel的最底部。当之后开始pop nextLevel时，最后才pop到x->left和x->right。换句话说，curLevel第一个被访问到的节点的子节点，将在nextLevel中最后被访问到。

2. 这里还需注意的是push left/right child进nextLevel的顺序。当curLevel从左向右访问时，应当先push(x->left)再push(x->right)，反之则应该先push(x->right)再push(x->left)。实现时可以用一个bool变量left2right来表示顺序，每访问完一层后反转left2right的值。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

class Solution { public: vector<vector<int> > zigzagLevelOrder(TreeNode *root) { vector<vector<int>> levelNodeValues; if(!root) return levelNodeValues; stack<TreeNode*> *curLevel = new stack<TreeNode*>(); stack<TreeNode*> *nextLevel = new stack<TreeNode*>(); curLevel->push(root); bool left2right = true; while(!curLevel->empty()) { vector<int> curLevelValues; while(!curLevel->empty()) { TreeNode *cur = curLevel->top(); curLevel->pop(); curLevelValues.push_back(cur->val); if(left2right) { if(cur->left) nextLevel->push(cur->left); if(cur->right) nextLevel->push(cur->right); } else { if(cur->right) nextLevel->push(cur->right); if(cur->left) nextLevel->push(cur->left); } } levelNodeValues.push_back(curLevelValues); // swap curLevel and nextLevel, no need to clear since curLevel is already empty stack<TreeNode*> *temp = curLevel; curLevel = nextLevel; nextLevel = temp; left2right = !left2right; } return levelNodeValues; } };