Binary Tree Level Order Traversal

Given a binary tree, return thelevel ordertraversal of its nodes' values. (ie, from left to right, level by level).
For example: Given binary tree[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
Note:
in Binary Tree Level Order Traversal II, the requirement is only different in getting the outcome as reverse order, namely bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]

Analysis

Recursive - DFS

关键在传入一个结果的list,因为list中元素的序号代表了层数(n+1)

Queue

利用一个Queue记录需要扫描的层(level)的节点数(number of nodes),依次存入每个节点的左子节点和右子节点到Queue中,读取时依次从Queue取出节点并存入该层sub list,每层扫描完后存入总的wrap list。

Solution

Top-down level order traversal

Using Recursive - DFS

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
levelOrderHelper(root, 0, result);
return result;
}
void levelOrderHelper(TreeNode root, int depth, List<List<Integer>> result) {
if (root == null) {
return;
}
if (depth == result.size()) {
result.add(new ArrayList<Integer>());
}
result.get(depth).add(root.val);
levelOrderHelper(root.left, depth + 1, result);
levelOrderHelper(root.right, depth + 1, result);
}
}

Using Queue - BFS

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

Bottom-up level order traversal

DFS - Recursive

public class Solution {
public List < List < Integer >> levelOrderBottom(TreeNode root) {
List < List < Integer >> wrapList = new LinkedList < List < Integer >> ();
levelMaker(wrapList, root, 0);
return wrapList;
}
public void levelMaker(List < List < Integer >> list, TreeNode root, int level) {
if (root == null) return;
if (level >= list.size()) {
list.add(0, new LinkedList < Integer > ());
}
levelMaker(list, root.left, level + 1);
levelMaker(list, root.right, level + 1);
list.get(list.size() - level - 1).add(root.val);
}
}

BFS - Queue

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<List<Integer>> wrapList = new LinkedList<List<Integer>>();
if(root == null) return wrapList;
queue.offer(root);
while(!queue.isEmpty()){
int levelNum = queue.size();
List<Integer> subList = new LinkedList<Integer>();
for(int i=0; i<levelNum; i++) {
if(queue.peek().left != null) queue.offer(queue.peek().left);
if(queue.peek().right != null) queue.offer(queue.peek().right);
subList.add(queue.poll().val);
}
wrapList.add(0, subList);
}
return wrapList;
}
}