**Leetcode 863. All Nodes Distance K in Binary Tree

本文主要是介绍**Leetcode 863. All Nodes Distance K in Binary Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://leetcode.com/contest/weekly-contest-91/problems/all-nodes-distance-k-in-binary-tree/

不错的题

最好写的做法还是，建反向边

class Solution {
public:void build(TreeNode* root, unordered_map<TreeNode*, TreeNode*>&redges) {if (!root) return;if (root->left) {redges[root->left] = root;build(root->left, redges);}if (root->right) {redges[root->right] = root;build(root->right, redges);}}vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {unordered_map<TreeNode*, TreeNode*> redges;build(root, redges);queue< pair<TreeNode*, int> > q;q.push( make_pair(target, 0) );vector<int> ans;unordered_set<TreeNode*> visit;visit.insert(target);while (!q.empty()) {pair<TreeNode*, int> tp = q.front();q.pop();if (tp.second == k) {ans.push_back( tp.first->val );continue;}if (tp.first->left && visit.find(tp.first->left) == visit.end()) {q.push(  make_pair(tp.first->left, tp.second + 1)  );visit.insert(tp.first->left);}if (tp.first->right && visit.find(tp.first->right) == visit.end()) {q.push(  make_pair(tp.first->right, tp.second + 1)  );visit.insert(tp.first->right);}if (redges.find(tp.first) != redges.end() && visit.find(redges[tp.first]) == visit.end() ) {q.push(  make_pair(redges[tp.first], tp.second + 1) );visit.insert(redges[tp.first]);}}return ans;}
};

考dfs功利的写法：

class Solution {
public:int getDown(TreeNode* root, int k, vector<int>&ans) {if (!root) return 0;if (k == 0) {ans.push_back(root->val);return 1;}k--;int ret = 0;if (root->left) {ret += getDown(root->left, k, ans);}if (root->right) {ret += getDown(root->right, k, ans);}return ret;}int dfs(TreeNode*root, TreeNode* target, int k, vector<int>&ret) {if (!root) return -1;if (root == target) {getDown(target, k, ret);return 1;}int d = dfs(root->left, target, k, ret);if (d >= 0) {if (d == k) {ret.push_back(root->val);} else {getDown(root->right,   k-d-1, ret);}return d + 1;}d = dfs(root->right, target, k, ret);if (d>=0) {if (d == k) {ret.push_back(root->val);} else {getDown(root->left,  k-d-1, ret);}return d+1;}return -1;}vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {vector<int> ret;if (!root) return ret;dfs(root, target, K, ret);return ret;}
};

这篇关于**Leetcode 863. All Nodes Distance K in Binary Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---