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

Question

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

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

如评论中所述，如果您的树已排序，则可以更快。

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

你几乎完成了你的尝试，首先你需要检查你是否有左节点或右节点，然后我检查左节点，如果找到节点，这棵树将 return ，如果没有，它将尝试正确的节点。它以递归方式执行此操作，以便访问每个可能的节点。

下面是一个工作示例..

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

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

虽然你的树也有问题，你的根左边的所有值都需要大于根的值，而根右边的所有值都需要小于，但它看起来像2在根的左边（谁的值为3）。

Answer 3

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 语句总是 returns 给调用者，在你的情况下，只有当你找到目标时，你才 returning returns回到 findPathFromRoot(currentNode.left, ...) 或 findPathFromRoot(currentNode.right, ...) 之一。但这些本身并不 return。因此，如果您在左侧或右侧子树中找到目标，则对代码的修复是return。

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

Return path from root to node in a binary tree

javascript

algorithm

tree

traversal