三刷 05/2022
DFS
Runtime: 1 ms, faster than 84.42% of Java online submissions for Binary Tree Level Order Traversal.
Memory Usage: 44 MB, less than 18.06% of Java online submissions for Binary Tree Level Order Traversal.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
dfs(root, result, 0);
return result;
}
private void dfs(TreeNode node, List<List<Integer>> result, int level) {
if (node == null) {
return;
}
if (level == result.size()) {
result.add(new ArrayList<>());
}
result.get(level).add(node.val);
dfs(node.left, result, level + 1);
dfs(node.right, result, level + 1);
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
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> que = new LinkedList<TreeNode>();
que.add(root);
TreeNode curr = null;
int size = 0;
while (!que.isEmpty()) {
List<Integer> subResult = new ArrayList<Integer>();
size = que.size();
for (int i = 0; i < size; i++) {
curr = que.poll();
subResult.add(curr.val);
if (curr.left != null) que.add(curr.left);
if (curr.right != null) que.add(curr.right);
}
result.add(subResult);
//subResult.clear();
}
return result;
}
}
二刷
45.53 %
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
TreeNode curr;
int size;
while (!que.isEmpty()) {
//#nodes in the current level
size = que.size();
List<Integer> level = new ArrayList<>();
while (size-- > 0) {
curr = que.poll();
level.add(curr.val);
if (curr.left != null) que.offer(curr.left);
if (curr.right != null) que.offer(curr.right);
}
result.add(level);
}
return result;
}
}
Version #2 DFS
beats 89.94%
public class Solution {
private List<List<Integer>> result;
public List<List<Integer>> levelOrder(TreeNode root) {
result = new ArrayList<List<Integer>>();
//an empty array of list
//if (root == null) return result;
dfs(root, 0);
return result;
}
private void dfs(TreeNode root, int level) {
if (root == null) return;
if (result.size() <= level) {
List<Integer> subResult = new ArrayList<Integer>();
subResult.add(root.val);
result.add(subResult);
} else {
result.get(level).add(root.val);
}
dfs(root.left, level + 1);
dfs(root.right, level + 1);
}
}
No comments:
Post a Comment