863. All Nodes Distance K in Binary Tree

Problem

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

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} target
 * @param {number} k
 * @return {number[]}
 */
var distanceK = function(root, target, k) {
    var nodes = [];
    var parents = [];
    visit(root, nodes, parents);

    var arr = [[nodes[target.val], '']];
    while (k > 0) {
        var newArr = [];
        for (var i = 0; i < arr.length; i++) {
            var [node, direction] = arr[i];
            node.left && direction !== 'left' && newArr.push([node.left, 'parent']);
            node.right && direction !== 'right' && newArr.push([node.right, 'parent']);
            parents[node.val] && direction !== 'parent' && newArr.push([
                parents[node.val],
                parents[node.val].left === node ? 'left' : 'right',
            ]);
        }
        arr = newArr;
        k--;
    }

    return arr.map(node => node[0].val);
};

var visit = function(root, nodes, parents) {
    nodes[root.val] = root;
    if (root.left) {
        parents[root.left.val] = root;
        visit(root.left, nodes, parents);
    }
    if (root.right) {
        parents[root.right.val] = root;
        visit(root.right, nodes, parents);
    }
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).