二刷 07/2022
Version #2 Recursive DFS
完全自己bug free写出来了感觉思路还是挺清晰的
关键是helper function返回的是target到当前node的距离
Time O(N)
Space O(N)
Runtime: 17 ms, faster than 53.43% of Java online submissions for All Nodes Distance K in Binary Tree.
Memory Usage: 42.8 MB, less than 72.00% of Java online submissions for All Nodes Distance K in Binary Tree.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
// given a root, if target is on its left, get the depth of the target from root, and find the depth of k - d - 1 nodes on the right subtree
// repeat the same process if the target is on its right
// if the node itself is the target, return all nodes that have depth k
List<Integer> result = new ArrayList<>();
findTarget(root, target, k, result);
return result;
}
// Returns the target depth from the current node
private Integer findTarget(TreeNode node, TreeNode target, int k, List<Integer> result) {
if (node == null) {
return null;
}
if (node == target) {
addNodeOfDepth(node, k, result);
return 0;
}
Integer left = findTarget(node.left, target, k, result);
if (left != null) {
// target is in the left subtree
if (left + 1 == k) {
result.add(node.val);
} else if (left + 1 < k) {
addNodeOfDepth(node.right, k - left - 2, result);
}
return left + 1;
}
Integer right = findTarget(node.right, target, k, result);
if (right != null) {
// target is in the right subtree
if (right + 1 == k) {
result.add(node.val);
} else if (right + 1 < k) {
addNodeOfDepth(node.left, k - right - 2, result);
}
return right + 1;
}
return null;
}
private void addNodeOfDepth(TreeNode node, int d, List<Integer> result) {
if (node == null) {
return;
}
if (d == 0) {
result.add(node.val);
return;
}
addNodeOfDepth(node.left, d - 1, result);
addNodeOfDepth(node.right, d - 1, result);
}
}
Version #1 Build Parent Mapping + BFS
非常straight forward的做法
复杂度没问题，performance有点慢
Time O(N)
Space O(N)
Runtime: 23 ms, faster than 16.07% of Java online submissions for All Nodes Distance K in Binary Tree.
Memory Usage: 43.1 MB, less than 56.39% of Java online submissions for All Nodes Distance K in Binary Tree.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
Map<TreeNode, TreeNode> parent = new HashMap<>();
buildGraph(root, parent, null);
Queue<TreeNode> que = new ArrayDeque<>();
Set<TreeNode> visited = new HashSet<>();
que.offer(target);
visited.add(target);
while (!que.isEmpty() && k != 0) {
int size = que.size();
k--;
while (size-- > 0) {
TreeNode curr = que.poll();
if (parent.containsKey(curr) && visited.add(parent.get(curr))) {
que.offer(parent.get(curr));
}
if (curr.left != null && visited.add(curr.left)) {
que.offer(curr.left);
}
if (curr.right != null && visited.add(curr.right)) {
que.offer(curr.right);
}
}
}
List<Integer> result = new ArrayList<>();
while (k == 0 && !que.isEmpty()) {
result.add(que.poll().val);
}
return result;
}
private void buildGraph(TreeNode node, Map<TreeNode, TreeNode> parent, TreeNode parentNode) {
if (node == null) {
return;
}
if (parentNode != null) {
parent.put(node, parentNode);
}
buildGraph(node.left, parent, node);
buildGraph(node.right, parent, node);
}
}
[1] 1 3
[0,1,null,3,2] 2 1
[3,5,1,6,2,0,8,null,null,7,4] 5 2
[0,1,null,null,2,null,3,null,4] 3 0
Tooooooo many edge cases that need to be taken care of carefully
80.11 %
class Solution {
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
List<Integer> result = new ArrayList<>();
// either in its subtree, or in the subtree of its lowest common ancestors
dfs(root, target, K, result);
return result;
}
// returns how many steps is current node away from target, -1 if target is not in the subtree of current node
private int dfs(TreeNode node, TreeNode target, int K, List<Integer> result) {
if (node == null) return -1;
if (node == target) {
find(node, K, result);
return 0;
}
int l = dfs(node.left, target, K, result);
int r = dfs(node.right, target, K, result);
if (l < 0 && r < 0) {
return -1;
} else if (l >= 0 && l + 1 == K || r >= 0 && r + 1 == K) {
result.add(node.val);
return -1;
} else if (l >= 0) {
find(node.right, K - l - 2, result);
return l + 1;
} else if (r >= 0) {
find(node.left, K - r - 2, result);
return r + 1;
}
return -1;
}
private void find(TreeNode node, int m, List<Integer> result) {
if (node == null || m < 0) return;
// find nodes that are m node from current node
if (m == 0) {
result.add(node.val);
return;
}
find(node.left, m - 1, result);
find(node.right, m - 1, result);
}
}
Version #1 Naive Build Graph + BFS
Stream 无解的慢。。。这个60%是去掉stream以后的performance
60.03 %
class Solution {
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
Map<TreeNode, List<TreeNode>> graph = new HashMap<>();
if (root != null) {
graph.put(root, new ArrayList<>());
}
build(root, graph);
Queue<TreeNode> que = new LinkedList<>();
Set<TreeNode> visited = new HashSet<>();
que.offer(target);
visited.add(target);
while (!que.isEmpty() && K > 0) {
int size = que.size();
while (size-- > 0) {
List<TreeNode> nexts = graph.get(que.poll());
for (TreeNode next : nexts) {
if (!visited.contains(next)) {
que.offer(next);
visited.add(next);
}
}
}
K--;
}
if (K == 0) {
return que.stream().map(node -> node.val).collect(Collectors.toList());
} else {
return new ArrayList<>();
}
}
private void build(TreeNode node, Map<TreeNode, List<TreeNode>> graph) {
if (node == null) {
return;
}
if (node.left != null) {
graph.put(node.left, new ArrayList<>());
graph.get(node).add(node.left);
graph.get(node.left).add(node);
build(node.left, graph);
}
if (node.right != null) {
graph.put(node.right, new ArrayList<>());
graph.get(node).add(node.right);
graph.get(node.right).add(node);
build(node.right, graph);
}
}
}
No comments:
Post a Comment