Today I have done leetcode's July LeetCoding Challenge with cpp.

July LeetCoding Challenge 11

Description

All Nodes Distance K in Binary Tree

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.

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]
Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.

Example 2:

Input: root = [1], target = 1, k = 3
Output: []

Constraints:

• The number of nodes in the tree is in the range [1, 500].
• 0 <= Node.val <= 500
• All the values Node.val are unique.
• target is the value of one of the nodes in the tree.
• 0 <= k <= 1000

Solution

class Solution {
  void buildGraph(TreeNode *root, vector<vector<int>> &neighbors) {
    int val = root->val;
    if(root->left) {
      neighbors[val].push_back(root->left->val);
      neighbors[root->left->val].push_back(val);
      buildGraph(root->left, neighbors);
    }
    if(root->right) {
      neighbors[val].push_back(root->right->val);
      neighbors[root->right->val].push_back(val);
      buildGraph(root->right, neighbors);
    }
  }
  void solve(
    int current,
    int parent,
    int k,
    vector<int> &answer,
    const vector<vector<int>> &neighbors
  ) {
    if(!k) {
      answer.push_back(current);
      return;
    }
    for(auto next : neighbors[current]) {
      if(parent == next) continue;
      solve(next, current, k - 1, answer, neighbors);
    }
  }
public:
  vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
    vector<vector<int>> neighbors(501);
    buildGraph(root, neighbors);
    vector<int> answer;
    solve(target->val, -1, k, answer, neighbors);
    return answer;
  }
};

// Accepted
// 57/57 cases passed (9 ms)
// Your runtime beats 38.57 % of cpp submissions
// Your memory usage beats 5.12 % of cpp submissions (16.9 MB)