Comment on page

102.Binary-Tree-Level-Order-Traversal

102. 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).
​
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]
]

代码

Approach 1: BFS

public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
​
if (root == null) return result;
​
Queue<TreeNode> queque = new LinkedList<TreeNode>();
queue.offer(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.offer(head.left);
}
if (head.right != null) {
queue.offer(head.right);
}
}
result.add(level);
}
​
return result;
}
}

Approach 2: DFS

class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> results = new ArrayList<List<Integer>>();
if (root == null) return results;
​
int maxLevel = 0;
while (true) {
List<Integer> level = new ArrayList<Integer>();
dfs(root, level, 0, maxLevel);
if (level.size() == 0) {
break;
}
​
results.add(level);
maxLevel++;
}
​
return results;
}
​
private void dfs(TreeNode root, List<Integer> level, int curtLevel, int maxLevel) {
if (root == null || curtLevel > maxLevel) return;
​
if (curtLevel == maxLevel) {
level.add(root.val);
return;
}
​
dfs(root.left, level, curtLevel + 1, maxLevel);
dfs(root.right, level, curtLevel + 1, maxLevel);
}
}

Approach 3; BFS, two queues

class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null) return result;
​
List<TreeNode> Q1 = new ArrayList<TreeNode>();
List<TreeNode> Q2 = new ArrayList<TreeNode>();
​
Q1.add(root);
while (Q1.size() != 0) {
List<Integer> level = new ArrayList<Integer>();
Q2.clear();
for (int i = 0; i < Q1.size(); i++) {
TreeNode node = Q1.get(i);
level.add(node.val);
if (node.left != null) {
Q2.add(node.left);
}
if (node.right != null) {
Q2.add(node.right);
}
}
​
List<TreeNode> temp = Q1;
Q1 = Q2;
Q2 = temp;
​
result.add(level);
}
​
return result;
}
}