内容简介:题目地址:题目描述:
题目地址:
https://leetcode-cn.com/probl...
题目描述:
给定一个二叉树(具有根结点 root), 一个目标结点 target ,和一个整数值 K 。
返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。
解答:
这一题显然是利用广度优先搜索来探测距离,然而树是一个有向图,我们需要一个无向图来进行广度优先搜索。
因此,先把树变成一个无向图,然后广度优先搜索这个无向图。距离不断增加,就可以找到每个节点和目标节点的距离。
java ac代码:
/**
* 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) {
List<Integer> ans = new ArrayList(1000);
HashMap<TreeNode,List<TreeNode>>map = new HashMap(1<<10);
dfs1(root,map);
dfs2(root,map);
ArrayDeque<TreeNode> deque = new ArrayDeque(100);
HashSet<TreeNode>set = new HashSet(1<<10);
HashMap<TreeNode,Integer> map2 = new HashMap(1<<10);
set.add(target);
deque.offer(target);
map2.put(target,0);
while(!deque.isEmpty())
{
TreeNode temp = deque.poll();
int num = map2.get(temp)+1;
for(TreeNode node:map.get(temp))
if(!set.contains(node))
{
set.add(node);
deque.offer(node);
map2.put(node,num);
}
}
for(Map.Entry<TreeNode,Integer> entry:map2.entrySet())
if(entry.getValue() == K)ans.add(entry.getKey().val);
return ans;
}
void dfs1(TreeNode root,HashMap<TreeNode,List<TreeNode>>map)
{
if(root == null)return;
map.put(root,new ArrayList(100));
dfs1(root.left,map);
dfs1(root.right,map);
}
void dfs2(TreeNode root,HashMap<TreeNode,List<TreeNode>>map)
{
if(root == null)return;
if(root.left != null)
{
map.get(root).add(root.left);
map.get(root.left).add(root);
}
if(root.right != null)
{
map.get(root).add(root.right);
map.get(root.right).add(root);
}
dfs2(root.left,map);
dfs2(root.right,map);
}
}
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
C++Templates中文版
David Vandevoorde、Nicolai M.Josuttis / 陈伟柱 / 人民邮电出版社 / 2008-2 / 69.00元
本书是C++模板编程的完全指南,旨在通过基本概念、常用技巧和应用实例3方面的有用资料,为读者打下C++模板知识的坚实基础。 全书共22章。第1章全面介绍了本书的内容结构和相关情况。第1部分(第2~7章)以教程的风格介绍了模板的基本概念,第2部分(第8~13章)阐述了模板的语言细节,第3部分(第14~18章)介绍了C++模板所支持的基本设计技术,第4部分(第19~22章)深入探讨了各种使用模板......一起来看看 《C++Templates中文版》 这本书的介绍吧!