diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /all_nodes_binary_tree.cpp | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'all_nodes_binary_tree.cpp')
-rw-r--r-- | all_nodes_binary_tree.cpp | 53 |
1 files changed, 53 insertions, 0 deletions
diff --git a/all_nodes_binary_tree.cpp b/all_nodes_binary_tree.cpp new file mode 100644 index 0000000..909352b --- /dev/null +++ b/all_nodes_binary_tree.cpp @@ -0,0 +1,53 @@ +// 863. All Nodes Distance K in Binary Tree +#include "leetcode.h" + +/* + * given the 'root' of a binary tree, the value of a target node 'target', and + * an integer 'k', return an array of the values of all nodes that have a + * distance 'k' from the target node. you can return the answer in any order. + */ + +class Solution { + void dfs(TreeNode *root, unordered_map<TreeNode *, TreeNode *> &back_edge, + TreeNode *target) { + if (!root || root == target) + return; + if (root->left) { + back_edge[root->left] = root; + dfs(root->left, back_edge, target); + } + if (root->right) { + back_edge[root->right] = root; + dfs(root->right, back_edge, target); + } + } + +public: + vector<int> distanceK(TreeNode *root, TreeNode *target, int k) { + unordered_map<TreeNode *, TreeNode *> back_edge; + unordered_set<TreeNode *> visited; + vector<int> ans; + dfs(root, back_edge, target); + queue<TreeNode *> q; + q.push(target); + while (!q.empty() && k >= 0) { + int s = q.size(); + while (s--) { + TreeNode *curr = q.front(); + int val = curr->val; + q.pop(); + visited.insert(curr); + if (!k) + ans.push_back(val); + if (!visited.count(back_edge[curr]) && back_edge[curr]) + q.push(back_edge[curr]); + if (!visited.count(curr->left) && curr->left) + q.push(curr->left); + if (!visited.count(curr->right) && curr->right) + q.push(curr->right); + } + k--; + } + return ans; + } +}; |