三刷 08/2022
Version #1 TreeMap - not optimal
一开始想的是需要有序
后来发现其实没有这个必要
看下面的O(N)解法
Time O(NlogN)
Space O(N)
Runtime: 7 ms, faster than 24.77% of Java online submissions for Binary Tree Vertical Order Traversal.
Memory Usage: 43.5 MB, less than 58.69% of Java online submissions for Binary Tree Vertical Order Traversal.
class Solution {
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
TreeMap<Integer, List<Integer>> map = new TreeMap<>();
Queue<Pair<TreeNode, Integer>> que = new ArrayDeque<>();
que.offer(new Pair<>(root, 0));
while (!que.isEmpty()) {
Pair<TreeNode, Integer> curr = que.poll();
TreeNode n = curr.getKey();
int col = curr.getValue();
map.putIfAbsent(col, new ArrayList<>());
map.get(col).add(n.val);
if (n.left != null) {
que.offer(new Pair<>(n.left, col - 1));
}
if (n.right != null) {
que.offer(new Pair<>(n.right, col + 1));
}
}
for (List<Integer> list : map.values()) {
result.add(list);
}
return result;
}
}
Version #2 Map with min and max column number
Time O(N)
Space O(N)
Runtime: 4 ms, faster than 74.52% of Java online submissions for Binary Tree Vertical Order Traversal.
Memory Usage: 43.5 MB, less than 58.69% of Java online submissions for Binary Tree Vertical Order Traversal.
class Solution {
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Map<Integer, List<Integer>> map = new HashMap<>();
Queue<Pair<TreeNode, Integer>> que = new ArrayDeque<>();
que.offer(new Pair<>(root, 0));
int minCol = 0, maxCol = 0;
while (!que.isEmpty()) {
Pair<TreeNode, Integer> curr = que.poll();
TreeNode n = curr.getKey();
int col = curr.getValue();
minCol = Math.min(minCol, col);
maxCol = Math.max(maxCol, col);
map.putIfAbsent(col, new ArrayList<>());
map.get(col).add(n.val);
if (n.left != null) {
que.offer(new Pair<>(n.left, col - 1));
}
if (n.right != null) {
que.offer(new Pair<>(n.right, col + 1));
}
}
for (int i = minCol; i <= maxCol; i++) {
result.add(map.get(i));
}
return result;
}
}
写了自己的pair class 没有用额外的queue
3.41 %
class Solution {
class Pair {
TreeNode node;
int colId;
public Pair(TreeNode node, int colId) {
this.node = node;
this.colId = colId;
}
}
public List<List<Integer>> verticalOrder(TreeNode root) {
if (root == null) return new ArrayList<>();
Map<Integer, List<Integer>> map = new HashMap<>();
int min = 0;
int max = 0;
Queue<Pair> que = new LinkedList<>();
que.offer(new Pair(root, 0));
while (!que.isEmpty()) {
Pair curr = que.poll();
if (curr.node != null) {
min = Math.min(min, curr.colId);
max = Math.max(max, curr.colId);
map.computeIfAbsent(curr.colId, list -> new ArrayList<>()).add(curr.node.val);
que.offer(new Pair(curr.node.left, curr.colId - 1));
que.offer(new Pair(curr.node.right, curr.colId + 1));
}
}
List<List<Integer>> result = new ArrayList<>();
for (int i = min; i <= max; i++) {
result.add(map.get(i));
}
return result;
}
}
一刷
首先说一下这个题dfs的解法是错的，因为在如图情况下
看到最后一层的2node 和第二层的 8node column都是1，但是由于是dfs遍历，所以必然先访问了2 后访问8，这个list最后的输出顺序就会变成[2, 8]。然而根据vertical order traversal的定义，一定是上面层先下面层后的，所以dfs不能满足题目要求。
//***************************wrong answer********************************
public class Solution {
private List<List<Integer>> result;
private Map<Integer, List<Integer>> hash;
private int min = Integer.MAX_VALUE;
private int max = Integer.MIN_VALUE;
public List<List<Integer>> verticalOrder(TreeNode root) {
result = new ArrayList<List<Integer>>();
hash = new HashMap<Integer, List<Integer>>();
dfs(root, 0);
for (int i = min; i <= max; i++) {
result.add(hash.get(i));
}
return result;
}
//***************************wrong answer********************************
private void dfs(TreeNode root, int col) {
if (root == null) return;
min = Math.min(min, col);
max = Math.max(max, col);
if (!hash.containsKey(col)) {
List<Integer> subResult = new ArrayList<Integer>();
subResult.add(root.val);
hash.put(col, subResult);
} else {
hash.get(col).add(root.val);
}
dfs(root.left, col - 1);
dfs(root.right, col + 1);
}
}
//***************************wrong answer********************************
下面说说正确的解法。BFS。其实跟DFS差不多，就是用一个queue,然后每次left child 的col 数为当前col - 1， right child 为当前 col + 1
写的时候特别愚蠢，一直报TLE还有崩溃，一开始以为是LC挂了。然而用了别人的答案跑完发现没问题
找了好久问题才发现每一次都在对root做操作。因为不是recursion所以应该是curr而不是root
beats 39.78%
public class Solution {
public List<List<Integer>> verticalOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (root == null) return result;
Queue<TreeNode> que = new LinkedList<TreeNode>();
Queue<Integer> colQue = new LinkedList<Integer>();
//key-#col, value-List<Integer>
Map<Integer, List<Integer>> hash = new HashMap<>();
que.add(root);
colQue.add(0);
int colMin = 0;
int colMax = 0;
while (!que.isEmpty()) {
TreeNode curr = que.poll();
int col = colQue.poll();
if (!hash.containsKey(col)) {
hash.put(col, new ArrayList<Integer>());
}
hash.get(col).add(curr.val);
if (curr.left != null) {
que.add(curr.left);
colQue.add(col - 1);
colMin = Math.min(colMin, col - 1);
}
if (curr.right != null) {
que.add(curr.right);
colQue.add(col + 1);
colMax = Math.max(colMax, col + 1);
}
}
for (int i = colMin; i <= colMax; i++) {
result.add(hash.get(i));
}
return result;
}
}
No comments:
Post a Comment