定一个二叉树（具有根结点 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
解题思路： target 已知，从target 出发，使用深度优先搜索去寻找与target 距离为 k 的所有结点，即深度为 k 的所有结点。
可知要寻找与target距离为k的结点，不应该只往子节点深度遍历，也要去深度遍历父节点。
用一个哈希表记录每个结点的父结点， 即创建hashMap，key表示子节点的值，value表示该子节点对应的父节点。
因为即遍历子节点也遍历父节点，可能会重复访问结点，为避免在深度优先搜索时重复访问结点，递归时额外传入来源结点from，在递归前比较目标结点是否与来源结点相同，不同的情况下才进行递归。
class Solution {
Map<Integer, TreeNode> hashParent = new HashMap<Integer, TreeNode>(); // 哈希表记录每个结点的父结点
List<Integer> returnList = new ArrayList<Integer>(); //要返回的所有的节点的值，即到target距离为K的所有结点
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
findParent(root);
findReturnList(target, null, 0, k);
return returnList;
}
public void findParent(TreeNode node) { // 创建子节点-父节点hash表
if (node.left != null) {
hashParent.put(node.left.val, node);
findParent(node.left);
}
if (node.right != null) {
hashParent.put(node.right.val, node);
findParent(node.right);
}
}
public void findReturnList(TreeNode root, TreeNode from, int depth, int k) { // 深度优先遍历
if(root == null) { //遍历到空结点，停止遍历；
return;
}
if(depth == k) { //遍历到深度为k，停止遍历；
returnList.add(root.val);
return;
}
if(root.left != from) { //即将要访问的左节点不是来源结点from
findReturnList(root.left, root, depth+1, k); //深度遍历左节点
}
if(root.right != from) { //即将要访问的右节点不是来源结点from
findReturnList(root.right, root, depth+1, k); //深度遍历右节点
}
if(hashParent.get(root.val) != from) { //即将要访问的父节点节点不是来源结点from
findReturnList(hashParent.get(root.val), root, depth+1, k); // //深度遍历父节点
}
}
}
网友评论