Paste_Image.png
My code:
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null)
return result;
Stack<TreeNode> s = new Stack<TreeNode>();
Stack<TreeNode> sSon = new Stack<TreeNode>();
s.push(root);
ArrayList<Integer> sample = new ArrayList<Integer>();
int count = 2;
while(!s.isEmpty()) {
TreeNode temp = s.pop();
sample.add(temp.val);
if (s.isEmpty()) {
if (count % 2 == 0) {
if (temp.left != null)
sSon.push(temp.left);
if (temp.right != null)
sSon.push(temp.right);
}
else {
if (temp.right != null)
sSon.push(temp.right);
if (temp.left != null)
sSon.push(temp.left);
}
result.add(sample);
sample = new ArrayList<Integer>();
s = sSon;
sSon = new Stack<TreeNode>();
count++;
}
else {
if (count % 2 == 0) {
if (temp.left != null)
sSon.push(temp.left);
if (temp.right != null)
sSon.push(temp.right);
}
else {
if (temp.right != null)
sSon.push(temp.right);
if (temp.left != null)
sSon.push(temp.left);
}
}
}
return result;
}
}
My test result:
Paste_Image.png
这道题目也需要动点脑子，总算还是做出来了。
其实和上面那道题目， Binary Tree Level Order Traversal 很类似，只不过改变了遍历的顺序。于是我决定改用Stack。但是也有些细节需要注意。
比如， 1,2,3,4,#,#,5
如果简单的把queue换成stack,会这样
第一次压入 1， 弹出。
第二次压入 3， 2， 弹出，所以访问顺序会是 2， 3. 就错了。
所以插入顺序应该反一反，压入 2， 3. 然后弹出3， 2.
第三次会压入5， 4. 弹出 4， 5.
这样的顺序就对了。
**
总结: stack, zigzag level traversal
**
Anyway, Good luck, Richardo!
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
ArrayList<List<Integer>> ret = new ArrayList<List<Integer>>();
if (root == null)
return ret;
int counter = 0;
Stack<TreeNode> s = new Stack<TreeNode>();
s.push(root);
while(!s.isEmpty()) {
ArrayList<Integer> group = new ArrayList<Integer>();
int size = s.size();
Stack<TreeNode> help = new Stack<TreeNode>();
if (counter % 2 == 0) {
for (int i = 0; i < size; i++) {
TreeNode temp = s.pop();
group.add(temp.val);
if (temp.left != null)
help.push(temp.left);
if (temp.right != null)
help.push(temp.right);
}
}
else {
for (int i = 0; i < size; i++) {
TreeNode temp = s.pop();
group.add(temp.val);
if (temp.right != null)
help.push(temp.right);
if (temp.left != null)
help.push(temp.left);
}
}
s = help;
counter++;
ret.add(group);
}
return ret;
}
}
想简单了一点，不能只用一个stack实现，得用两个。
不难。
有时候做题不能想当然。像这道题目，s弹出元素对其操作时，再次把子结点插入该栈中，造成了问题。一开始盲目想的时候都没有想到。
Anyway, Good luck, Richardo!
My code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
if (root == null) {
return ret;
}
Stack<TreeNode> curr = new Stack<TreeNode>();
Stack<TreeNode> next = new Stack<TreeNode>();
curr.push(root);
int counter = 0;
while (!curr.isEmpty()) {
int size = curr.size();
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < size; i++) {
TreeNode node = curr.pop();
list.add(node.val);
if (counter % 2 == 0) {
if (node.left != null) {
next.push(node.left);
}
if (node.right != null) {
next.push(node.right);
}
}
else {
if (node.right != null) {
next.push(node.right);
}
if (node.left != null) {
next.push(node.left);
}
}
}
ret.add(list);
counter++;
curr = next;
next = new Stack<TreeNode>();
}
return ret;
}
}
没什么好说的，感觉就是体力活，没难度。
Anyway, Good luck, Richardo! -- 09/06/2016
