题目

给定一个二叉树（具有根结点 root），一个目标结点 target ，和一个整数值 k 。
返回到目标结点 target 距离为 k 的所有结点的值的列表。答案可以以 任何顺序 返回。

示例 1：
[中等] 863. 二叉树中所有距离为 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
输出: []

解答 & 代码

解法一：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    vector<TreeNode*> path;
    vector<int> result;
    // 从 root 节点开始往下寻找距离为 k 的节点
    void dfsFindDisKNodes(TreeNode* root, int k)
    {
        if(root == NULL)
            return;
        if(k == 0)
            result.push_back(root->val);
        dfsFindDisKNodes(root->left, k - 1);
        dfsFindDisKNodes(root->right, k - 1);
    }
    // 在以 root 为根节点的树中寻找节点 target，并记录路径
    void findTargetNode(TreeNode* root, TreeNode* target, vector<TreeNode*>& nodePath)
    {
        if(root == NULL)
            return;
        nodePath.push_back(root);
        if(root == target)
        {
            path.assign(nodePath.begin(), nodePath.end());
            return;
        }
        findTargetNode(root->left, target, nodePath);
        findTargetNode(root->right, target, nodePath);
        nodePath.pop_back();
    }
public:
    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        /* 答案分为两部分：一部分位于 target 节点下面，另一部分从 target 往上经过某个祖先节点转到另一棵子树*/
        /* 1. 从 target 节点开始往下寻找距离为 k 的节点 */ 
        dfsFindDisKNodes(target, k);
        /* 2. 从 target 往上经过某个祖先节点转到另一棵子树，距离为 k 的节点*/
        // 记录从 root 到 target 的路径
        vector<TreeNode*> nodePath;
        findTargetNode(root, target, nodePath);
        // 以路径上 target 的每个祖先节点开始转弯到另一棵子树
        int len = path.size();
        for(int i = 1; i < k && len - i - 1 >= 0; ++i)
        {
            // 选择一个祖先节点
            TreeNode* curNode = path[len - i - 1];
            // 转到另一棵子树
            curNode = curNode->left == path[len - i] ? curNode->right : curNode->left;
            // 从该节点开始往下寻找距离为 k - i - 1 的节点
            dfsFindDisKNodes(curNode, k - i - 1);
        }
        // 记录路径上和 target 距离恰好为 k 的祖先节点（无需转弯到另一棵子树）
        if(k > 0 && len - k - 1 >= 0)
            result.push_back(path[len - k - 1]->val);
        return result;
    }
};

复杂度分析：设二叉树节点数为 n

时间复杂度 O(n)：
空间复杂度 O(log n)：

执行结果：

执行结果：通过

执行用时：8 ms, 在所有 C++ 提交中击败了 44.35% 的用户
内存消耗：12.1 MB, 在所有 C++ 提交中击败了 94.68% 的用户

解法二：BFS（推荐）

将二叉树转化为一幅图，然后 BFS（层序遍历）求图中和 target 节点距离为 k 的所有节点

二叉树转化为图：用哈希表 **parentMap** 记录每个节点的父节点，这样在每个节点都能访问所有与其相邻的节点（左子节点、右子节点、父节点）

用哈希表 **visited** 记录所有已被访问过的节点，防止 BFS 走回头路

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
  // 哈希表，记录每个节点的父节点，key = 节点值，val = 父节点
  unordered_map<int, TreeNode*> parentMap;

  // 深度优先遍历所有节点，将每个节点对应的父节点存储到哈希表 parentMap
  void dfs(TreeNode* root, TreeNode* parent)
  {
      if(root == NULL)
          return;

      parentMap[root->val] = parent;
      dfs(root->left, root);
      dfs(root->right, root);
  }
public:
  vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
      vector<int> result;
      if(root == NULL || target == NULL)
          return result;
      // 遍历所有节点，，将每个节点对应的父节点存储到哈希表 parentMap
      dfs(root, NULL);

      // BFS，从 target 结点开始层序遍历，找到距离为 k 的节点（即遍历 k 步/层）
      queue<TreeNode*> nodeQ;
      nodeQ.push(target);
      unordered_set<int> visited;        // 哈希表，存储已被访问过的节点，防止 BFS 走回头路
      visited.insert(target->val);
      while(!nodeQ.empty() && k >= 0)
      {
          int levelCnt = nodeQ.size();
          for(int i = 0; i < levelCnt; ++i)
          {
              TreeNode* cur = nodeQ.front();
              nodeQ.pop();
              if(k == 0)        // 距离为 k 的节点，存储到 result
                  result.push_back(cur->val);

              // 分别向左子节点、右子节点、父节点扩散
              if(cur->left && visited.find(cur->left->val) == visited.end())
              {
                  nodeQ.push(cur->left);
                  visited.insert(cur->left->val);
              }
              if(cur->right && visited.find(cur->right->val) == visited.end())
              {
                  nodeQ.push(cur->right);
                  visited.insert(cur->right->val);
              }
              if(parentMap[cur->val] && visited.find(parentMap[cur->val]->val) == visited.end())
              {
                  nodeQ.push(parentMap[cur->val]);
                  visited.insert(parentMap[cur->val]->val);
              }
          }
          --k;                // 更新剩余步数/层数
      }
      return result;
  }
};

复杂度分析：设二叉树节点数为 n

时间复杂度 O(n)：
空间复杂度 O(n)：

执行结果：

执行结果：通过

执行用时：8 ms, 在所有 C++ 提交中击败了 44.35% 的用户
内存消耗：12.8 MB, 在所有 C++ 提交中击败了 42.58% 的用户