- Binary Tree Level Order Traversal
class Solution {
//BFS 最要在Node进入queue前就进行非空判断，使得进入queue的node本身都非null
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<List<Integer>> result = new LinkedList<List<Integer>>();
if(root == null) return result;
queue.offer(root);
while(!queue.isEmpty()) {
int num_on_level = queue.size();
List<Integer> cur_result = new LinkedList<Integer>();
for(int i = 0; i < num_on_level; i++) {
TreeNode cur = queue.poll();
if(cur.left != null) queue.add(cur.left);
if(cur.right != null) queue.add(cur.right);
cur_result.add(cur.val);
}
result.add(cur_result);
}
return result;
}
}
- Binary Tree Zigzag Level Order Traversal
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<List<Integer>> result = new LinkedList<List<Integer>>();
if(root == null) return result;
boolean order = true;
queue.offer(root);
while(!queue.isEmpty()) {
int num_on_level = queue.size();
List<Integer> cur_result = new LinkedList<Integer>();
for(int i = 0; i < num_on_level; i++) {
TreeNode cur = queue.poll();
if(cur.left != null) queue.add(cur.left);
if(cur.right != null) queue.add(cur.right);
// add result to cur_result
if(order) cur_result.add(cur.val);
else cur_result.add(0, cur.val);
}
result.add(cur_result);
order = order ? false : true;
}
return result;
}
}
- Binary Tree Level Order Traversal II
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<List<Integer>> result = new LinkedList<List<Integer>>();
if(root == null) return result;
queue.offer(root);
while(!queue.isEmpty()) {
int num_on_level = queue.size();
List<Integer> cur_result = new LinkedList<Integer>();
for(int i = 0; i < num_on_level; i++) {
TreeNode cur = queue.poll();
if(cur.left != null) queue.add(cur.left);
if(cur.right != null) queue.add(cur.right);
cur_result.add(cur.val);
}
result.add(0, cur_result);
}
return result;
}
}
- Find Largest Value in Each Tree Row
class Solution {
//BFS 最要在Node进入queue前就进行非空判断，使得进入queue的node本身都非null
public List<Integer> largestValues(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<Integer> result = new LinkedList<Integer>();
if(root == null) return result;
queue.offer(root);
while(!queue.isEmpty()) {
int largest_elem = Integer.MIN_VALUE;
int num_on_level = queue.size();
for(int i = 0; i < num_on_level; i++) {
TreeNode cur = queue.poll();
largest_elem = Math.max(largest_elem, cur.val);
if(cur.left != null) queue.add(cur.left);
if(cur.right != null) queue.add(cur.right);
}
result.add(largest_elem);
}
return result;
}
}
