leetcode 863.二叉树中所有距离为 K 的结点

863.二叉树中所有距离为 K 的结点

文章目录

• 863.二叉树中所有距离为 K 的结点
• 一、题目
• • 1.题目描述
  • 2.基础框架
  • 3.解题思路
  • 4.总结

一、题目

原题链接：863. 二叉树中所有距离为 K 的结点

1.题目描述

给定一个二叉树（具有根结点 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

示例 2:

输入: root = [1], target = 1, k = 3
输出: []

提示:

• 节点数在 [1, 500] 范围内
• 0 <= Node.val <= 500
• Node.val 中所有值 不同
• 目标结点 target 是树上的结点。
• 0 <= k <= 1000

2.基础框架

C++基础框架代码如下:

vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
}

3.解题思路

• 题目分析

1. 题目目标是返回目标节点开始距离k的所有结点。
2. 该二叉树可以看成是无向图。
3. 首先遍历整个二叉树，建立无向图，因为题目中提示了所有结点值都不同，所以无向图中的结点类型为整型就好了。
4. 然后从target结点的值开始进行广度优先遍历，深度为2的所有结点作为返回值。

• 实现代码：

  #define N 501
  using namespace std;
  class Solution {
  public:
      vector<int> edges[N];
      void Traversal(TreeNode* root, TreeNode* pre)	//遍历二叉树建立无向图
      {
          if (root == nullptr) return ;
          edges[root->val].push_back(pre->val);
          edges[pre->val].push_back(root->val);
          Traversal(root->left, root);
          Traversal(root->right, root);
          return ;
      }
      void bfs(vector<int>& res, int start, int k)
      {
          if (k == 0) res.push_back(start);
          queue<int> q;
          q.push(start);
          unique_ptr<int[]> rec(new int[N]);
          unique_ptr<int[]> depth(new int[N]);
          memset(rec.get(), 0, N * sizeof(int));
          memset(depth.get(), 0, N * sizeof(int));
          depth[start] = 0;
          
          while (!q.empty())
          {
              int v = q.front();
              q.pop();
              ++rec[v];
              for (int i = 0; i < edges[v].size(); ++i)
              {
                  int u = edges[v][i];
                  if (!rec[u])
                  {
                      q.push(u);
                      depth[u] = depth[v] + 1;
                      if (depth[u] == k)
                          res.push_back(u);
                  }
              }
          }
          return ;
      }
      
      vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
          vector<int> res;
          Traversal(root->left, root);
          Traversal(root->right, root);
          bfs(res, target->val, k);
          return res;
      }
  };
  

4.总结

​  知识点：广度优先遍历，无向图，二叉树。