返回二叉树中从根到节点的路径

Question

我正在尝试完成一些看似简单但难以实现的事情。给定一个二叉树和一个节点，返回路径。我在下面尝试过，但我真的卡住了。我也不完全确定一旦找到目标节点如何退出递归函数。

const tree = {
  val: 3,
  left: {
    val: 5,
    left: {
      val: 6,
      left: null,
      right: null
    },
    right: {
      val: 2,
      left: null,
      right: null
    }
  },
  right: {
    val: 1,
    left: null,
    right: null
  }
};
const findPathFromRoot = (currentNode, targetNode, path) => {
  path + currentNode.val;
  if (currentNode === targetNode) {
    return path + targetNode.val;
  }
  findPathFromRoot(currentNode.left, targetNode, path);
  findPathFromRoot(currentNode.right, targetNode, path);
}
const target = tree.left.right;
console.log(findPathFromRoot(tree, target, '')); // should return "352"

Answer 1

const findPathFromRoot = (root, target, path = "") => {
  if (root === null) {
    return null;
  }
  path = path + root.val;
  if (root === target) {
    return path;
  }
  const left = findPathFromRoot(root.left, target, path);
  const right = findPathFromRoot(root.right, target, path);
  return left || right;
};

为什么会这样？

return 语句总是返回给调用方，在您的情况下，只有当你找到目标时，你才会返回，而目标又返回到 findPathFromRoot(currentNode.left， ...( 或 findPathFromRoot(currentNode.right， ...(。但这些不会自己回来。因此，对代码的修复是在左侧或右侧子树中找到目标时返回。

Answer 2

就像评论中提到的，如果你的树被排序了，这可以做得更快。

照原样，每个节点都需要检查。

你几乎在那里你尝试

的东西，首先你需要检查你是否有左节点或右节点，然后我检查左节点，如果这找到这个树下的节点将返回，如果没有，它将尝试右节点。 它以递归方式执行此操作，以便访问每个可能的节点。

下面是一个工作示例。

const tree = {
  val: 3,
  left: {
    val: 5,
    left: {
      val: 6,
      left: null,
      right: null
    },
    right: {
      val: 2,
      left: null,
      right: null
    }
  },
  right: {
    val: 1,
    left: null,
    right: null
  }
};
const findPathFromRoot = (currentNode, targetNode, path) => {
  path += currentNode.val;
  if (currentNode === targetNode) {
    return path;
  }
  let ret = null;
  if (currentNode.left) ret = findPathFromRoot(currentNode.left, targetNode, path);
  if (currentNode.right && !ret) ret = findPathFromRoot(currentNode.right, targetNode, path);
  return ret;
}
const target = tree.left.right;
console.log(findPathFromRoot(tree, target, '')); // should return "352"

Answer 3

您需要输入逻辑来决定是从当前节点的值向左还是向右移动，并根据该逻辑使用 currentNode.left 或 currentNode.right 调用您的方法。然后在获得 null 值时返回(这意味着目标在树中不存在(，或者在 currentNode.value === 目标时返回。

不过，您的树也存在一个问题，根左侧的所有值都需要大于根的值，根右侧

的所有值都需要更小，但看起来 2 在根的左侧(谁的值是 3(。