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
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] ]Solution 1: iterative BFS use stack
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
Deque<TreeNode> s1=new LinkedList<>();
Deque<TreeNode> s2=new LinkedList<>();
List<List<Integer>> res=new ArrayList<>();
if (root==null) return res;
s1.push(root);
while (!s1.isEmpty()) {
List<Integer> one=new ArrayList<>();
while (!s1.isEmpty()) {
TreeNode x=s1.pop();
one.add(x.val);
if (x.left!=null) s2.push(x.left);
if (x.right!=null) s2.push(x.right);
}
res.add(one);
if (s2.isEmpty()) break;
List<Integer> two=new ArrayList<>();
while (!s2.isEmpty()) {
TreeNode x=s2.pop();
two.add(x.val);
if (x.right!=null) s1.push(x.right);
if (x.left!=null) s1.push(x.left);
}
res.add(two);
}
return res;
}
}
Solution 2: recursive using DFS
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res=new ArrayList<>();
dfs(root,0,res);
return res;
}
private void dfs(TreeNode x, int d, List<List<Integer>> res) {
if (x==null) return;
if (d==res.size()) res.add(new LinkedList<Integer>());
if (d%2==0) res.get(d).add(x.val);
else res.get(d).add(0,x.val);
dfs(x.left,d+1,res);
dfs(x.right,d+1,res);
}
}
没有评论:
发表评论