LeetCode 863. 二叉树中所有距离为 K 的结点（公共祖先/ DFS+BFS）数据结构与算法Michael是个半路程序员-

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 

注意，输入的 "root" 和 "target" 实际上是树上的结点。 上面的输入仅仅是对这些对象进行了序列化描述。   提示： 给定的树是非空的，且最多有 K 个结点。 树上的每个结点都具有唯一的值 0 <= node.val <= 500 。 目标结点 target 是树上的结点。 0 <= K <= 1000. 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/all-nodes-distance-k-in-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

2.1 公共祖先

参考了官网题解区

• 按照二叉树的数组实现思想，把各个节点编号
• 知道target的编号 pt 了，遍历所有节点编号 pi
• 当 pt != pi 时，较大的一边，往上移动一层，(p-1)/2，同时距离 +1，直到相等，找到最近公共祖先
• 时间复杂度
  $O(nlogn)$

  O(nlogn)

class Solution {     unordered_map<TreeNode*, int> pos; public:     vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {         vector<int> ans; dfs(root,0); int pt, pi, dis = 0; for(auto posi : pos) {             pt = pos[target];             pi = posi.second;             dis = 0; while(pt != pi) { if(pt < pi)                     pi = (pi-1)/2; else                     pt = (pt-1)/2;                 dis++; } if(dis == K)                 ans.push_back(posi.first->val); } return ans; } void dfs(TreeNode* root, int p) { if(!root) return;         pos[root] = p; dfs(root->left, 2*p+1); dfs(root->right, 2*p+2); } }; 

12 ms 15.2 MB

2.2 建图+BFS

• dfs 建立每个节点与父节点的路径
• bfs 查找第 k 层节点
• 时间复杂度
  $O(n)$

  O(n)

class Solution {     unordered_map<TreeNode*, TreeNode*> f; public:     vector<int> distanceK(TreeNode* root, TreeNode* target, int K) { dfs(root, NULL);         vector<int> ans;         unordered_set<TreeNode*> visited;         queue<TreeNode*> q;         q.push(target);         visited.insert(target); int dis = 0, size;         TreeNode* tp; while(!q.empty()) { if(dis == K) break;             size = q.size(); while(size--) {                 tp = q.front();                 q.pop(); if(tp->left && !visited.count(tp->left)) {                     q.push(tp->left);                     visited.insert(tp->left); } if(tp->right && !visited.count(tp->right)) {                     q.push(tp->right);                     visited.insert(tp->right); } if(f[tp] && !visited.count(f[tp])) {                     q.push(f[tp]);                     visited.insert(f[tp]); } }             dis++; } while(!q.empty()) {             ans.push_back(q.front()->val);             q.pop(); } return ans; } void dfs(TreeNode* root, TreeNode* father) { if(!root) return;         f[root] = father;//建立父节点连接 dfs(root->left, root); dfs(root->right, root); } }; 

8 ms 15.8 MB