- Binary Tree Level Order Traversal
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
dfs(result, root, 0);
return result;
}
public void dfs(List<List<Integer>> result, TreeNode root, int level) {
if (root == null) return;
if (level == result.size()) {
result.add(new LinkedList<Integer>());
}
result.get(level).add(root.val);
dfs(result, root.left, level+1);
dfs(result, root.right, level+1);
}
}
- Binary Tree Zigzag Level Order Traversal
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
dfs(result, root, 0);
return result;
}
public void dfs(List<List<Integer>> result, TreeNode root, int level) {
if (root == null) return;
if (level == result.size()) {
result.add(new LinkedList<Integer>());
}
List<Integer> list = result.get(level);
if(level % 2 == 0) list.add(root.val);
else list.add(0, root.val);
dfs(result, root.left, level + 1);
dfs(result, root.right, level + 1);
}
}
- Find Largest Value in Each Tree Row
class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> result = new ArrayList<Integer>();
dfs(root, result, 0);
return result;
}
private void dfs(TreeNode node, List<Integer> result, int level) {
if(node == null) {
return;
}
if(level == result.size()) {
// expand result list to next level
result.add(node.val);
}
else {
// update max
result.set(level, Math.max(result.get(level), node.val));
}
dfs(node.left, result, level + 1);
dfs(node.right, result, level + 1);
}
}
