Вернуть путь от корня к узлу в двоичном дереве - PullRequest
Новая
       21

Вернуть путь от корня к узлу в двоичном дереве

0 голосов
/ 30 апреля 2019

Я пытаюсь сделать что-то, что кажется простым, но возникают проблемы при его реализации. Если задано двоичное дерево и узел, верните путь. Я попытался сделать это ниже, но я действительно застрял. Я также не совсем уверен, как выйти из рекурсивной функции, когда найду целевой узел. 

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"

Ответы [ 3 ]

2 голосов
/ 30 апреля 2019 
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, ...).Но они не возвращаются.Поэтому исправление в вашем коде должно вернуться, если вы найдете цель в левом или правом поддереве.

1 голос
/ 30 апреля 2019

Как упоминалось в комментариях, если бы ваше дерево было отсортировано, это можно было бы сделать быстрее.

Как есть, каждый узел должен быть проверен ..

Вы были почти там с тем, что вы пытались, сначала вам нужно проверить, есть ли у вас левый или правый узел, затем я проверяю левый узел, если он найдет узел внизу, это дерево вернется, если это не так Затем попробуйте правильный узел. Он делает это рекурсивно, чтобы каждый возможный узел посещался.

Ниже приведен рабочий пример. 

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"
0 голосов
/ 30 апреля 2019

Вам необходимо ввести логику, чтобы решить, следует ли перемещаться влево или вправо от значения текущего узла и вызывать ваш метод с помощью currentNode.left или currentNode.right в зависимости от этой логики.Затем вернитесь либо, когда получите нулевое значение (это означает, что цель не существует в дереве), или вернитесь, когда currentNode.value === target.

Хотя с вашим деревом также есть проблема, всезначения слева от вашего корня должны быть больше, чем значение корня, и все значения справа от корня должны быть меньше, но похоже, что 2 слева от корня (чье значение равно 3).

...