题目:
题解:
1. 迭代法:
使用bfs,对应层判断一下奇偶,决定在表头还是表尾添加元素就可以了。
2. 递归法:
使用递归解法的时候(dfs),根据层数是奇数还是偶数,来判断添加到开头还是添加到末尾。
代码:
1. 迭代法:
/** * code103 */
import java.util.*;
public class code103 {
public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<List<Integer>>();
}
List<List<Integer>> res = new ArrayList<List<Integer>>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int count = 0;
while (!queue.isEmpty()) {
count++;
int size = queue.size();
List<Integer> tmp = new ArrayList<Integer>();
for (int i = 0; i < size; i++) {
TreeNode t = queue.poll();
tmp.add(t.val);
if (t.left != null) {
queue.offer(t.left);
}
if (t.right != null) {
queue.offer(t.right);
}
}
if (count % 2 == 1) {
res.add(tmp);
} else if (count % 2 == 0) {
Collections.reverse(tmp);
res.add(tmp);
}
}
return res;
}
public static void main(String[] args) {
System.out.println("***************************************");
Integer nums[] = { 3, 9, 20, null, null, 15, 7 };
TreeNode tree = ConstructTree.constructTree(nums);
TreeOperation.show(tree);
System.out.println("***************************************");
List<List<Integer>> res = zigzagLevelOrder(tree);
System.out.println(res.toString());
System.out.println("***************************************");
}
}
2. 递归法:
/** * code103 */
import java.util.*;
public class code103 {
public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<List<Integer>>();
}
List<List<Integer>> res = new ArrayList<>();
dfs(1, root, res);
return res;
}
public static void dfs(int index, TreeNode root, List<List<Integer>> res) {
if (res.size() < index) {
res.add(new ArrayList<Integer>());
}
if (index % 2 == 1) {
res.get(index - 1).add(root.val);
} else if (index % 2 == 0) {
res.get(index - 1).add(0, root.val);
}
if (root.left != null) {
dfs(index + 1, root.left, res);
}
if (root.right != null) {
dfs(index + 1, root.right, res);
}
}
public static void main(String[] args) {
System.out.println("***************************************");
Integer nums[] = { 3, 9, 20, null, null, 15, 7 };
TreeNode tree = ConstructTree.constructTree(nums);
TreeOperation.show(tree);
System.out.println("***************************************");
List<List<Integer>> res = zigzagLevelOrder(tree);
System.out.println(res.toString());
System.out.println("***************************************");
}
}