🐌1. 题目描述

:::info 给定三个参数

  1. 二叉树的头节点head，
  2. 树上某个节点target，
  3. 正整数K

从target开始，可以向上走或者向下走，返回于target的距离是K的所有节点。 ::: 示例

💡2. 解决思路

  1. 从二叉树的指定节点target开始，既可以向上也可以向下走，说明需要对该二叉树结构进行功能增强，每个节点应该知道自己的父节点是谁，因此需要个结构保存每个节点的父节点信息的对应关系，这样达到一个无向图的效果。
  2. 然后基于增强功能的树结构，查找距离target节点长度为K的所有节点，图的宽度优先遍历（队列实现），找到第K层的所有节点就是输出答案。
  3. 为了方便输出某一层的所有的节点，对入队的一层的所有节点进行批处理操作。
  4. 为了避免节点重复入栈，需要设置一个Set集合，用于节点的注册，避免重复入栈。

🚩3. 代码实现

  1. public class Code08_DistanceKNodes {
  3.     // 二叉树结构
  4.     public static class Node {
  5.         public int value;
  6.         public Node left;
  7.         public Node right;
  9.         public Node(int v) {
  10.             value = v;
  11.         }
  12.     }
  14.     public static List<Node> distanceKNodes(Node root, Node target, int K) {
  15.         // 存储节点的父子关系
  16.         HashMap<Node, Node> parents = new HashMap<>();
  17.         // 头节点的父节点为null
  18.         parents.put(root, null);
  19.         // 构建root二叉树的父子节点关系
  20.         createParentMap(root, parents);
  21.         // 队列用于实现宽度优先遍历
  22.         Queue<Node> queue = new LinkedList<>();
  23.         // 注册集合用于存放访问过的节点信息
  24.         HashSet<Node> visited = new HashSet<>();
  25.         // 基于二叉树结构和父子关系映射表map来实现从target节点开始的宽度优先遍历
  26.         queue.offer(target);   // target入队
  27.         visited.add(target);   // 将入队的注册到集合中
  29.         int curLevel = 0;
  30.         // 存放返回结果
  31.         List<Node> ans = new ArrayList<>();
  32.         while (!queue.isEmpty()) {
  33.             // 当前层的节点个数
  34.             int size = queue.size();
  36.             // 对同层的节点进行同批处理
  37.             while (size-- > 0) {
  38.                 Node cur = queue.poll();
  39.                 // 如果是K层则加入到结果中，K层表示距离为target节点距离为K
  40.                 if (curLevel == K) {
  41.                     ans.add(cur);
  42.                 }
  43.                 if (cur.left != null && !visited.contains(cur.left)) {
  44.                     visited.add(cur.left);
  45.                     queue.offer(cur.left);
  46.                 }
  47.                 if (cur.right != null && !visited.contains(cur.right)) {
  48.                     visited.add(cur.right);
  49.                     queue.offer(cur.right);
  50.                 }
  51.                 if (parents.get(cur) != null && !visited.contains(parents.get(cur))) {
  52.                     visited.add(parents.get(cur));
  53.                     queue.offer(parents.get(cur));
  54.                 }
  55.             }
  56.             curLevel++;
  57.             if (curLevel > K) {
  58.                 break;
  59.             }
  60.         }
  61.         return ans;
  62.     }
  64.     /**
  65.      * 递归创建父子对应关系
  66.      * @param cur      当前节点
  67.      * @param parents  存储指定父子节点的对应关系，key为子节点，value为父节点
  68.      */
  69.     public static void createParentMap(Node cur, HashMap<Node, Node> parents) {
  70.         if (cur == null) {
  71.             return;
  72.         }
  73.         if (cur.left != null) {
  74.             parents.put(cur.left, cur);
  75.             createParentMap(cur.left, parents);
  76.         }
  77.         if (cur.right != null) {
  78.             parents.put(cur.right, cur);
  79.             createParentMap(cur.right, parents);
  80.         }
  81.     }
  83.     // 测试
  84.     public static void main(String[] args) {
  85.         Node n0 = new Node(0);
  86.         Node n1 = new Node(1);
  87.         Node n2 = new Node(2);
  88.         Node n3 = new Node(3);
  89.         Node n4 = new Node(4);
  90.         Node n5 = new Node(5);
  91.         Node n6 = new Node(6);
  92.         Node n7 = new Node(7);
  93.         Node n8 = new Node(8);
  94.         n3.left = n5;
  95.         n3.right = n1;
  96.         n5.left = n6;
  97.         n5.right = n2;
  98.         n1.left = n0;
  99.         n1.right = n8;
  100.         n2.left = n7;
  101.         n2.right = n4;
  102.         Node root = n3;
  103.         Node target = n5;
  104.         int K = 2;
  105.         List<Node> ans = distanceKNodes(root, target, K);
  106.         for (Node o1 : ans) {
  107.             System.out.println(o1.value);
  108.         }
  109.     }
  110. }

🔑4. 考点

二叉树遍历图的深度优先遍历