103. Binary Tree Zigzag Level Order Traversal
二刷。
BFS,基本习惯上用Iterative的做法来做,就是QUEUE。
/**
* 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>> res = new ArrayList<List<Integer>>();
if(root == null) return res;
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.add(root);
boolean left = false;
int cur = 1;
int total = 0;
TreeNode temp = null;
List<Integer> tempList = new ArrayList<Integer>();
while(!q.isEmpty())
{
temp = q.poll();
cur--;
tempList.add(temp.val);
if(temp.left != null)
{
q.add(temp.left);
total++;
}
if(temp.right != null)
{
q.add(temp.right);
total++;
}
if(cur == 0)
{
cur = total;
total = 0;
if(!left)
{
res.add(new ArrayList<Integer>(tempList));
left = !left;
}
else
{
Collections.reverse(tempList);
res.add(new ArrayList<Integer>(tempList));
left = !left;
}
tempList = new ArrayList<Integer>();
}
}
return res;
}
}
reverse一个LIST的函数是Collections.reverse(list),不是list.reverse()。。那个是StringBuilder。
看一刷说还有Recursivley的做法。
然后试试发现还真行。。
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root)
{
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(root == null) return res;
helper(res,root,0);
for(int i = 1; i < res.size();i+=2)
{
Collections.reverse(res.get(i));
}
return res;
}
public void helper(List<List<Integer>> res, TreeNode root, int level)
{
if(root == null) return;
List<Integer> tempList = new ArrayList<Integer>();
if(level > res.size()-1) res.add(new ArrayList<Integer>());
res.get(level).add(root.val);
helper(res,root.left,level+1);
helper(res,root.right,level+1);
}
}
beat 95%..
三刷。
尽量加的时候就弄好顺序,别最后排序。。
Recursion:
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
dfs(root, res, true, 0);
return res;
}
public void dfs(TreeNode root, List<List<Integer>> res, boolean fromLeft, int level) {
if (root == null) return;
if (level == res.size()) {
res.add(new ArrayList<>());
}
if (fromLeft) {
res.get(level).add(root.val);
} else {
res.get(level).add(0,root.val);
}
dfs(root.left, res, !fromLeft, level + 1);
dfs(root.right, res, !fromLeft, level + 1);
}
}
Iteration:
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
res.add(new ArrayList<>());
TreeNode temp = null;
boolean fromLeft = true;
int left = 1; // how many nodes left in this level
int total = 0;
int level = 0;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
temp = q.poll();
if (fromLeft) {
res.get(level).add(temp.val);
} else {
res.get(level).add(0, temp.val);
}
if (temp.left != null) {
q.offer(temp.left);
total ++;
}
if (temp.right != null) {
q.offer(temp.right);
total ++;
}
if (-- left == 0) {
left = total;
total = 0;
level ++;
fromLeft = !fromLeft;
if (!q.isEmpty()) {
res.add(new ArrayList<>());
}
}
}
return res;
}
}