✅ 0ms | ✨ O(N) | 🏆 Most Optimal Solution | 👍 Double Tree Walk
Intuition\n Describe your first thoughts on how to solve this problem. \nIt\'s quite easy to find the children of a node with distance $k$ in a binary tree. The
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIt\'s quite easy to find the **children** of a node with distance $k$ in a binary tree. Therefore we implement this as `CollectValues()`.\n\nTo find the other nodes that are with distance $k$ to the `target`, we just need to find:\n  1. **children** nodes with distance $k - 1$ to the parent of the `target`\n  2. **children** nodes with distance $k - 2$ to the parent of the parent of the `target`\n  3. $...$\n\nNote we must exclude the path from `parent n` towards the `target` and only choose the other side.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe first do a simple tree walk to find the path from `root` to `target`. Then we do another tree walk to collect values.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$\\Theta(N)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$\\Theta(\\log N)$$ if the tree is balanced\n$$\\Theta(N)$$ if it\'s degenerated.\n\n# Code\n```\n\nbool SearchPath(const TreeNode* root, const TreeNode* target, vector<const TreeNode*>& path) {\n  if (root == nullptr) {\n    return false;\n  }\n  path.push_back(root);\n  if (root == target) {\n    return true;\n  }\n  if (SearchPath(root->left, target, path) || SearchPath(root->right, target, path)) {\n    return true;\n  }\n  path.pop_back();\n  return false;\n}\n\nvector<const TreeNode*> FindPath(const TreeNode* root, const TreeNode* target) {\n  vector<const TreeNode*> path;\n  SearchPath(root, target, path);\n  return path;\n}\n\nvoid CollectValues(const TreeNode* node, int depth, vector<int>& values) {\n  if (node == nullptr) {\n    return;\n  }\n  if (depth == 0) {\n    values.push_back(node->val);\n    return;\n  }\n  --depth;\n  CollectValues(node->left, depth, values);\n  CollectValues(node->right, depth, values);\n}\n\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}\n * };\n */\nclass Solution {\npublic:\n  vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {\n    vector<const TreeNode*> path = FindPath(root, target);\n    vector<int> values;\n    CollectValues(target, k, values);\n    --k;\n    for (int i = path.size() - 1; i >= 1; --i) {\n      // Now we are collecting children nodes for path[i - 1]\n      // with distance `k`, but excluding the direction of path[i]\n      if (k == 0) {\n        values.push_back(path[i - 1]->val);\n        break;\n      }\n      const TreeNode* node = path[i - 1]->left == path[i] ? path[i - 1]->right : path[i - 1]->left;\n      CollectValues(node, k - 1, values);\n      --k;\n    }\n    return values;\n  }\n};\n```
['Binary Tree', 'C++']