兰州市网站建设_网站建设公司_展示型网站_seo优化

Problem: 863. All Nodes Distance K in Binary Tree 二叉树中所有距离为 K 的结点

解题过程

使用图论的，将二叉树变成邻接表图，然后从目标node出发，访问所有的nodes，计算距离的，若是距离==k，则放入每个列表

Code

/** * 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 { public: vector<vector<int>> tr; vector<bool> status; void dfs(TreeNode* root) { if(root == nullptr) return; dfs(root->left); dfs(root->right); if(root->left != nullptr) { tr[root->val].push_back(root->left->val); tr[root->left->val].push_back(root->val); } if(root->right != nullptr) { tr[root->val].push_back(root->right->val); tr[root->right->val].push_back(root->val); } } vector<int> ret; void recursion(int start, int k) { if(k == 0) { ret.push_back(start); } status[start] = true; int next; for(int i = 0; i < tr[start].size(); i++) { next = tr[start][i]; if(status[next] == false) { recursion(next, k-1); } } } vector<int> distanceK(TreeNode* root, TreeNode* target, int k) { tr.resize(600); status.assign(600, false); dfs(root); recursion(target->val, k); return ret; } };