NC370. 距离是K的二叉树节点
描述
示例1
输入:
{3,5,2,4,6,0,7,1,8},5,2
输出:
[1,8,2]
C++ 解法, 执行用时: 4ms, 内存消耗: 432KB, 提交时间: 2022-07-10
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param target int整型
* @param k int整型
* @return int整型vector
*/
int tar;
vector<int> ans;
void Road_Del(TreeNode* root,int k){
if(root==NULL) return;//递归出口
k--;
if(k==0) {//找到距离为k的节点了，放入答案中
ans.push_back(root->val);
return;
}
Road_Del(root->left,k);//继续找
Road_Del(root->right,k);
}
int Find_Knode(TreeNode* root,int k){//返回-1代表没有找到，n代表找到了且距离为n
if(root==NULL) return -1;
if(root->val==tar){
Road_Del(root->left,k);
Road_Del(root->right,k);
return 0;
}
int left=Find_Knode(root->left,k);
int right=Find_Knode(root->right,k);
if(left>=0){//左边找到目标
if(left+1==k){//这个节点就是
ans.push_back(root->val);//没有往上的必要了
return -1;
}
Road_Del(root->right,k-left-1);
return left+1;
}
if(right>=0){//右边找到目标
if(right+1==k){//这个节点就是
ans.push_back(root->val);
return -1;
}
Road_Del(root->left,k-right-1);
return right+1;
}
return -1;
}
vector<int> distanceKnodes(TreeNode* root, int target, int k) {
// write code here
//根据公共节点的题的启发，本题可分为两条路
//1.遍历到目标节点后继续遍历，每遍历一层就k--
//2.通过返回某个值向上递归来区分目标值在当前节点的左子树还是右子树，
//在没有目标值的子树和第一种方法一样k--遍历
tar=target;
Find_Knode(root,k);
return ans;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 436KB, 提交时间: 2022-08-06
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param target int整型
* @param k int整型
* @return int整型vector
*/
int tar;
vector<int> ans;
void Road_Del(TreeNode *root,int k)
{
if(root==NULL)
return;
k--;
if(k==0)
{
ans.push_back(root->val);
return;
}
Road_Del(root->left, k);
Road_Del(root->right, k);
}
int Find_Knode(TreeNode *root,int k)
{
if(root==NULL)
return -1;
if(root->val==tar)
{
Road_Del(root->left, k);
Road_Del(root->right, k);
return 0;
}
int left=Find_Knode(root->left, k);
int right=Find_Knode(root->right,k);
if(left>=0)
{
if(left+1==k)
{
ans.push_back(root->val);
return -1;
}
Road_Del(root->right, k-left-1);
return left+1;
}
if(right>=0)
{
if(right+1==k)
{
ans.push_back(root->val);
return -1;
}
Road_Del(root->left, k-right-1);
return right+1;
}
return -1;
}
vector<int> distanceKnodes(TreeNode* root, int target, int k) {
// write code here
tar=target;
Find_Knode(root, k);
return ans;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 436KB, 提交时间: 2022-06-17
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param target int整型
* @param k int整型
* @return int整型vector
*/
struct MyNode{
TreeNode* node;
int tag;
};
MyNode myNode;
vector<int> res;
stack<MyNode> path;
int target;
int len;
int stage;
void dfs(TreeNode* root){
myNode.node=root;
path.push(myNode);
if(stage == 1){
if(root->val == target)
return;
}else if(stage == 2){
if(path.size() == len)
res.push_back(path.top().node->val);
}
if(root->left!=NULL){
path.top().tag=0;
dfs(root->left);
}else if(root->right!=NULL){
path.top().tag=1;
dfs(root->right);
}else{
path.pop();
while(!path.empty()&&(path.top().tag==1 || path.top().node->right==NULL)){
path.pop();
}
if(!path.empty()){
path.top().tag=1;
dfs(path.top().node->right);
}
return;
}
}
vector<int> distanceKnodes(TreeNode* root, int target, int k) {
// write code here
this->target = target;
len = k+1;
stage = 1;
dfs(root);
TreeNode* pos = path.top().node;
if(path.size()>=len){
for(int i=0; i<len-1; i++){
path.pop();
}
res.push_back(path.top().node->val);
}
while(!path.empty())
path.pop();
stage = 2;
dfs(pos);
return res;
}
};
C 解法, 执行用时: 4ms, 内存消耗: 440KB, 提交时间: 2022-07-12
void P(struct TreeNode* root, int k, int **result, int *maxResultSize, int *returnSize) {
if (root == NULL) {
return;
} else if (k == 0) {
if (*returnSize >= *maxResultSize) {
(*maxResultSize) += 10;
*result = (int *)realloc(*result, sizeof(int) * (*maxResultSize));
}
(*result)[*returnSize] = root->val;
(*returnSize) += 1;
return;
} else {
P(root->left, k-1, result, maxResultSize, returnSize);
P(root->right, k-1, result, maxResultSize, returnSize);
}
}
void F(struct TreeNode* root, int *depth, int target,
int k, int **result, int *maxResultSize, int *returnSize) {
if (root == NULL) {
*depth = -1;
return;
} else if (root->val == target) {
*depth = 0;
P(root, k, result, maxResultSize, returnSize);
return;
} else {
F(root->left, depth, target, k, result, maxResultSize, returnSize);
if (*depth >= 0) {
if (*depth == k - 1) {
if (*returnSize >= *maxResultSize) {
(*maxResultSize) += 10;
*result = (int *)realloc(*result, sizeof(int) * (*maxResultSize));
}
(*result)[*returnSize] = root->val;
(*returnSize) += 1;
} else if (*depth < k - 1) {
P(root->right, k-2-*depth, result, maxResultSize, returnSize);
}
(*depth) += 1;
} else {
F(root->right, depth, target, k, result, maxResultSize, returnSize);
if (*depth >= 0) {
if (*depth == k - 1) {
if (*returnSize >= *maxResultSize) {
(*maxResultSize) += 10;
*result = (int *)realloc(*result, sizeof(int) * (*maxResultSize));
}
(*result)[*returnSize] = root->val;
(*returnSize) += 1;
} else if (*depth < k - 1) {
P(root->left, k-2-*depth, result, maxResultSize, returnSize);
}
(*depth) += 1;
}
}
}
}
int* distanceKnodes(struct TreeNode* root, int target, int k, int* returnSize ) {
int maxResultSize = 10;
int *result = (int *)malloc(sizeof(int) * maxResultSize);
*returnSize = 0;
int depth = 0;
F(root, &depth, target, k, &result, &maxResultSize, returnSize);
return result;
}
C++ 解法, 执行用时: 4ms, 内存消耗: 520KB, 提交时间: 2022-06-29
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param target int整型
* @param k int整型
* @return int整型vector
*/
vector<int> distanceKnodes(TreeNode* root, int target, int k) {
// write code here
findParent(root);
findTarget(root, target);
findAns(target_node, NULL, 0, k);
return ans;
}
private:
void findParent(TreeNode* root) {
if (root->left != nullptr) {
parent[root->left->val] = root;
findParent(root->left);
}
if (root->right != nullptr) {
parent[root->right->val] = root;
findParent(root->right);
}
}
void findTarget(TreeNode* root, int target) {
if (root == nullptr) {
return;
}
findTarget(root->left, target);
findTarget(root->right, target);
if (root->val == target) {
target_node = root;
return;
}
}
void findAns(TreeNode* root, TreeNode* from, int d, int k) {
if (root == nullptr) {
return;
}
if (d == k) {
ans.emplace_back(root->val);
return;
}
if (root->left != from) {
findAns(root->left, root, d + 1, k);
}
if (root->right != from) {
findAns(root->right, root, d + 1, k);
}
if (parent[root->val] != from) {
findAns(parent[root->val], root, d + 1, k);
}
}
private:
unordered_map<int, TreeNode*> parent;
vector<int> ans;
TreeNode* target_node;
};