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]]
简单的bfs而已，不过在bfs的过程中应该注意将相应的数组reverse一下，其实都到最终结果之后在隔行reverse也是可以的，下面给出非递归的版本，用递归同样也很好实现：
1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution {11 struct Node12 {13 TreeNode * node;14 int level;15 Node(){}16 Node(TreeNode * n, int lv)17 : node(n), level(lv){}18 };19 public:20 vector > zigzagLevelOrder(TreeNode* root) {21 vector > ret;22 if(!root) return ret;23 vector tmp;24 int dep = 0;25 queue q;26 q.push(Node(root, 0));27 while(!q.empty()){28 Node tmpNode = q.front(); //非递归的使用bfs，借助队列特性29 if(tmpNode.node->left)30 q.push(Node(tmpNode.node->left, tmpNode.level + 1));31 if(tmpNode.node->right)32 q.push(Node(tmpNode.node->right, tmpNode.level + 1));33 if(dep < tmpNode.level){34 if(dep % 2){35 reverse(tmp.begin(), tmp.end());36 }37 ret.push_back(tmp);38 tmp.clear();39 dep = tmpNode.level;40 }41 tmp.push_back(tmpNode.node->val);42 q.pop();43 }44 if(dep % 2){45 reverse(tmp.begin(), tmp.end());46 }47 ret.push_back(tmp);48 return ret;49 }50 };
java版本的代码如下所示，这里用的是dfs而非bfs，在最后重新reverse就可以了：
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 public List > zigzagLevelOrder(TreeNode root) {12 List > ret = new ArrayList >();13 dfs(ret, 1, root);14 for(int i = 0; i < ret.size(); ++i){15 if(i%2 != 0) Collections.reverse(ret.get(i));16 }17 return ret;18 }19 20 void dfs(List >ret, int dep, TreeNode root){21 if(root == null)22 return;23 if(ret.size() < dep){24 List list = new ArrayList ();25 list.add(root.val);26 ret.add(list);27 }else28 ret.get(dep - 1).add(root.val);29 dfs(ret, dep + 1, root.left);30 dfs(ret, dep + 1, root.right);31 }32 }