742.Nearest to leaf node
Find the treenode whose value == k first, then can use BFS to find the nearest leaf node to this target node.(Clever mind, once find target node, guaranteed to be nearest node).
TreeNode left, right’s writing will ensure that as if the target node is not dfind, it will continually add the current node and parent node to the hashMap, only ignore those node where their depth are deeper than the current node.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38public class Solution {
public int findClosestLeaf(TreeNode root, int k) {
Map<TreeNode,TreeNode> parent = new HashMap<>();
TreeNode target = findDFS(parent, k, root);
Queue<TreeNode> visit = new LinkedList<>();
visit.offer(target);
Set<TreeNode>stat = new HashSet<>();
stat.add(target);
while(visit.size()>0) {
TreeNode cur = visit.poll();
if(cur.left==null&&cur.right==null) return cur.val;
if(cur.left!=null&& stat.add(cur.left)) {
visit.offer(cur.left);
}
if(cur.right!=null && stat.add(cur.right)) {
visit.offer(cur.right);
}
if(parent.containsKey(cur) && stat.add(parent.get(cur))) {
visit.offer(parent.get(cur));
}
}
}
public TreeNode findDFS(Map<TreeNode,TreeNode>parent, int k, TreeNode root) {
if(root.val == k) return root;
if(root.left != null) {
parent.put(root.left,root);
TreeNode left = findDFS(parent,k,root.left);
if(left!=null) return left;
}
if(root.right != null) {
parent.put(root.right,root);
TreeNode right = findDFS(parent,k,root.right);
if(right!=null) return right;
}
return null;
}
}
250. Count Univalue Subtrees
Subtree should include all of its left&&right treenodes. can’t be single branch of one node… Notice that this type of problem all use post traversal to solve…
compare each leaves with their parent nodes and follow along the path to get upper side.Only when both left&&right subtree all counted as univalue can it be counted as univalue
Why use int[] as params?
Here int[] works like a wrap. When you pass (int[])arr to a method, it creates a new reference point to the same object as arr and pass the new reference to the method. Hence when you change for example arr[0] in the method call, since both of the references point to the same object, it will reflect on arr in the parent call;
int is a primitive type, you pass a int variable to a method it simply makes a copy of the variable and pass it to the method.
Thus, use a array can be equivlant to use a global variable.