leetcode863. 二叉树中所有距离为 K 的结点
给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。
返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
输出：[7,4,1]
解释：
所求结点为与目标结点（值为 5）距离为 2 的结点，
值分别为 7，4，以及 1
提示：
- 给定的树是非空的，且最多有 K 个结点。
- 树上的每个结点都具有唯一的值 0 <= node.val <= 500 。
- 目标结点 target 是树上的结点。
- 0 <= K <= 1000.
思路一:转化成图,再变成bfs
遍历一次树,主要是为了把当前节点的父节点记录下来,这样bfs时候可以访问到父节点了.
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
38
39
40
41
42
43
| class Solution {
HashMap<TreeNode,TreeNode>map=new HashMap<>();
ArrayList<Integer>list=new ArrayList<>();
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
init(root,null);
Queue<TreeNode>queue=new LinkedList<>();
queue.offer(target);
Set<TreeNode>set=new HashSet<>();
set.add(target);
while(!queue.isEmpty()){
int size=queue.size();
if(K==0){
for(TreeNode node:queue){
list.add(node.val);
}
}
for(int i=0;i<size;i++){
TreeNode node=queue.poll();
if(node.left!=null&&!set.contains(node.left)){
queue.offer(node.left);
set.add(node.left);
}
if(node.right!=null&&!set.contains(node.right)){
queue.offer(node.right);
set.add(node.right);
}
if(map.get(node)!=null&&!set.contains(map.get(node))){
queue.offer(map.get(node));
set.add(map.get(node));
}
}
K--;
}
return list;
}
public void init(TreeNode curNode,TreeNode parent){
if(curNode==null)return;
map.put(curNode,parent);
init(curNode.left,curNode);
init(curNode.right,curNode);
}
}
|
思路二:霍夫曼树
看到评论区有提示说霍夫曼树,我试着写了一下,左子树代表 1,右子树代表 3 .用字符串表示每个节点的编号,任意两个节点之间的距离需要用前缀计算.
比如 113,和 131.前缀是1,所以是13(两位)+31(两位)=4(位).我是一条边一个编号,根节点编号为””.也就是空字符串.
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
38
39
40
41
42
| class Solution {
HashMap<TreeNode,String>map=new HashMap<>();
public TreeNode targetNode=null;
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
map.put(root,"");
init(root,"");
return traverse(target,map.get(target),K);
}
public List<Integer> traverse(TreeNode target,String targetString,int k){
ArrayList<Integer>list=new ArrayList<>();
for(TreeNode key:map.keySet()){
int diff=diff(map.get(key),targetString);
if(diff==k)list.add(key.val);
}
return list;
}
public int diff(String s1,String s2){
int length=Math.min(s1.length(),s2.length());
int i=0;
for(i=0;i<length;i++){
if(s1.charAt(i)!=s2.charAt(i))break;
}
return s1.length()-i+s2.length()-i;
}
public void init(TreeNode node,String s){
if(node==null)return;
if(node.left!=null){
StringBuffer sbf=new StringBuffer(s);
sbf.append("1");
map.put(node.left,new String(sbf));
init(node.left,new String(sbf));
}
if(node.right!=null){
StringBuffer sbf=new StringBuffer(s);
sbf.append("3");
map.put(node.right,new String(sbf));
init(node.right,new String(sbf));
}
}
}
|
霍夫曼树2
题解用long整数编码,而不是字符串,减少了一次for循环,并且根节点编号为1.
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
38
39
40
41
42
| class Solution {
Map<Integer,Long> map = new HashMap<>();
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
List<Integer> list = new ArrayList<>();
codeTree(root,1);
long targetCode = 0;
for(Integer key:map.keySet()) {
if(key==target.val) {
targetCode = map.get(key);
break;
}
}
for(Integer key:map.keySet()) {
if(distanceCode(map.get(key),targetCode)==K) {
list.add(key);
}
}
return list;
}
public void codeTree(TreeNode root, long value){
if(root==null) return;
map.put(root.val, value);
codeTree(root.right, value*10+1);
codeTree(root.left, value*10+3);
}
public int distanceCode (long val, long target) {
long sameL = 0;
long more = Math.max(val, target);
long less = Math.min(val, target);
long L1 =(long)Math.log10(more)+1;
long L2 =(long)Math.log10(less)+1;
double temp = Math.abs(less*(Math.pow(10, L1 - L2)) - more);
sameL = (temp==0)?L1:L1 - (long)(Math.log10(temp+1)) - 1;
return (int)(L1 + L2 - 2*sameL);
}
}
|
leetcode 58/100