Time: 60 minutes

The idea is still very simple. First use DFS to add a parent to each node, and find the required target by the way.

Then starting from the target, use DFS to find a point K away from the target.

Find all the parents of target in turn and use DFS to find the point with a distance K.

The reason why it takes so much time is that after finding the parent, DFS is used to find it back, causing a memory overflow.

The way to avoid this is to find the parent, and if it is the left child, go to the right child (because the left child has already been found), otherwise go the other way.

var distanceK = function(root, target, K) {
    var node = null    var res = []
    var dfs = function (root) {
        if (root === target) {
            node = root        }
        if (root.left) {
            root.left.parent = root            dfs(root.left)
        }
        if (root.right) {
            root.right.parent = root            dfs(root.right)
        }
    }
    dfs(root)
    var search = function (root,index) {
        if (!root) return
        if (index === K) {
            res.push(root.val)
        }
        root.left && search(root.left,index + 1)
        root.right &&  search(root.right,index + 1)
    }
    search(node,0)
    var index = 1    // The initial distance between the parent node and node is 1 while(index <= K && node.parent) {
        if(index === K) {
            res.push(node.parent.val)
            break        }
        if (node.parent.left === node) {
            search(node.parent.right,++index)
        } else {
            search(node.parent.left,++index)
        }
        node = node.parent
    }
    return res
};

A few points to note

  1. Be careful about checking for null points
  2. The parent node may be the node you need to find. If the parent node is already at distance k, there is no need to search further.