Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

BFS

思路： 典型的BFS, 使用queue. 两层循环，外层判断queue 是否为空，内层for循环queue的size，然后逐个弹出node， 把左右儿子再压入。 注意开始的root == null 的判断。

时间复杂度： O(N)
空间复杂度： O(w) where w is maximum width of Binary Tree.

public class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<List<Integer>>();Queue<TreeNode> queue = new LinkedList<TreeNode>();if (root == null) {return result;}queue.add(root);while (queue.peek() != null) {int size = queue.size();List<Integer> list = new ArrayList<Integer>();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();list.add(node.val);if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}}result.add(list);}return result;}
}

---

Binary Tree Level Order Traversal 2

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

思路： BFS, 因为是bottom-up, 所以每次加入list都加到开头：bfs.add(0, level);

public class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> bfs = new ArrayList<List<Integer>>();Queue<TreeNode> queue = new LinkedList<TreeNode>();if (root == null) {return bfs;}queue.add(root);while(!queue.isEmpty()){ArrayList<Integer> level = new ArrayList<Integer>();int size = queue.size();for(int i = 0; i < size; i++){TreeNode head = queue.poll();level.add(head.val);if(head.left != null){queue.add(head.left);}if(head.right != null){queue.add(head.right);}}bfs.add(0, level);}return bfs;}
}

---

Binary Tree Zigzag Level Order Traversal

思路： 设置一个flag,来确定该层是从左往右，还是从右往左。Collections.reverse(level) 变换方向。

public class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<List<Integer>>();if(root == null){return result;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);int flag = -1;while(queue.peek() != null){flag = 0 - flag;int size = queue.size();List<Integer> level = new ArrayList<Integer>();for(int i = 0; i < size; i++){TreeNode head = queue.poll();level.add(head.val);if(head.left != null){queue.offer(head.left);}if(head.right != null){queue.offer(head.right);}}if(flag == -1){Collections.reverse(level);}result.add(level);}return result;}}