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

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 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 2

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;
};

为什么这样做？

返回语句总是返回给调用者，在你的情况下，只有在找到目标时才返回，而目标又返回到findPathFromRoot（currentNode.left，...）或findPathFromRoot（currentNode.right，... ）。但这些并没有归还。因此，如果您在左侧或右侧子树中找到目标，则会修复代码。

Answer 3

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

但是你的树也有问题，根的左边的所有值都需要大于根的值，并且根的右边的所有值都需要更小，但看起来像2在左边根（谁的价值是3）。