北京企业建设网站公司简介,线上推广员是干什么的兼职,网站推广排名怎么做,wordpress相关文章插件文章目录1. 题目2. 解题2.1 公共祖先2.2 建图BFS1. 题目
给定一个二叉树#xff08;具有根结点 root#xff09;#xff0c; 一个目标结点 target #xff0c;和一个整数值 K 。
返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。
示例 …
文章目录1. 题目2. 解题2.1 公共祖先2.2 建图BFS1. 题目
给定一个二叉树具有根结点 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 的结点
值分别为 74以及 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)O(nlogn)
class Solution {unordered_mapTreeNode*, int pos;
public:vectorint distanceK(TreeNode* root, TreeNode* target, int K) {vectorint 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;elsept (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*p1);dfs(root-right, 2*p2);}
};12 ms 15.2 MB
2.2 建图BFS
dfs 建立每个节点与父节点的路径bfs 查找第 k 层节点时间复杂度O(n)O(n)O(n)
class Solution {unordered_mapTreeNode*, TreeNode* f;
public:vectorint distanceK(TreeNode* root, TreeNode* target, int K) {dfs(root, NULL);vectorint ans;unordered_setTreeNode* visited;queueTreeNode* 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
