Lstmxx的空间

863. 二叉树中所有距离为 K 的结点

给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。

返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。

链接

tips

用图来解就好了

/**
 * 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) {
  const res = []
  if (root === null) return root
  const nodeQue = [root]
  let findTarget = null
  while(nodeQue.length > 0) {
    const node = nodeQue.shift()
    if (node === target) {
      findTarget = node
      break
    }
    if (node.left) {
      node.left.parent = node
      nodeQue.push(node.left)
    }
    if (node.right) {
      node.right.parent = node
      nodeQue.push(node.right)
    }
  }
  function dfs(node, depth) {
    if (node === null || node.isRead) return
    node.isRead = true
    if (depth === k) {
      res.push(node.val)
      return
    }
    node.parent && dfs(node.parent, depth + 1)
    dfs(node.left, depth + 1)
    dfs(node.right, depth + 1)
  }
  dfs(findTarget, 0)
  return res
};