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

链接：863.二叉树中所有距离为K的结点
难度：Medium
标签：树、深度优先搜索、广度优先搜索、哈希表、二叉树
简介：给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。

题解 1 - typescript

• 编辑时间：2021-07-25
• 执行用时：88ms
• 内存消耗：39.9MB
• 编程语言：typescript
• 解法介绍：向上寻找，向下寻找。

function distanceK(root: TreeNode | null, target: TreeNode | null, k: number): number[] {
  const ans: number[] = [];
  find();
  return ans;
  function find(node: TreeNode | null = root): number {
    if (node === null) return -1;
    if (node === target) {
      dfs(node);
      return k - 1;
    }
    let step = find(node.left);
    if (step !== -1) {
      if (step === 0) {
        ans.push(node.val);
        return -1;
      } else {
        dfs(node.right, step - 1);
        return step - 1;
      }
    }
    step = find(node.right);
    if (step !== -1) {
      if (step === 0) {
        ans.push(node.val);
        return -1;
      } else {
        dfs(node.left, step - 1);
        return step - 1;
      }
    }
    return -1;
  }
  function dfs(node: TreeNode | null, level = k): void {
    if (node === null) return;
    if (level === 0) {
      ans.push(node.val);
    } else {
      dfs(node.left, level - 1);
      dfs(node.right, level - 1);
    }
  }
}

题解 2 - typescript

• 编辑时间：2021-07-28
• 执行用时：88ms
• 内存消耗：40.1MB
• 编程语言：typescript
• 解法介绍：递归。

function distanceK(root: TreeNode | null, target: TreeNode | null, k: number): number[] {
  const ans: number[] = [];
  find(root);
  return ans;
  function find(node: TreeNode | null): number {
    if (node === null) return -1;
    if (node === target) {
      dfs(node, k);
      return k - 1;
    }
    let distance = find(node.left);
    if (distance !== -1) {
      if (distance === 0) ans.push(node.val);
      else {
        dfs(node.right, distance - 1);
        return distance - 1;
      }
      return -1;
    }
    distance = find(node.right);
    if (distance !== -1) {
      if (distance === 0) ans.push(node.val);
      else {
        dfs(node.left, distance - 1);
        return distance - 1;
      }
    }
    return -1;
  }
  function dfs(node: TreeNode | null, k: number): void {
    if (node === null) return;
    if (k === 0) {
      ans.push(node.val);
    } else {
      dfs(node.left, k - 1);
      dfs(node.right, k - 1);
    }
  }
}