Поиск путей в суммировании двоичного дерева поиска до целевого значения

Ответ 1

Пройдите через дерево из корня и выполните сборку по порядку всех сумм пути. Используйте хеш-таблицу, чтобы сохранить возможные пути, основанные на node и только вниз. Мы можем построить все пути, проходящие через node от себя и к его детским путям.

Вот psuedo-код, который реализует выше, но хранит только суммы, а не фактические пути. Для самих путей вам нужно сохранить конец node в хэш-таблице (мы знаем, где он начинается, и есть только один путь между двумя узлами в дереве).

function findsum(tree, target)
  # Traverse the children
  if tree->left
    findsum(tree.left, target)
  if tree->right
    findsum(tree.right, target)

  # Single node forms a valid path
  tree.sums = {tree.value}

  # Add this node to sums of children
  if tree.left
    for left_sum in tree.left.sums
      tree.sums.add(left_sum + tree.value)
  if tree.right
    for right_sum in tree.right.sums
      tree.sums.add(right_sum + tree.value)

  # Have we formed the sum?
  if target in tree.sums
    we have a path

  # Can we form the sum going through this node and both children?
  if tree.left and tree.right
    for left_sum in tree.left.sums
      if target - left_sum in tree.right.sums
        we have a path

  # We no longer need children sums, free their memory
  if tree.left
    delete tree.left.sums
  if tree.right
    delete tree.right.sums

Это не использует тот факт, что дерево является деревом поиска, поэтому оно может применяться к любому двоичному дереву.

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

Ответ 2

Мой ответ O(n^2), но я считаю, что он является точным и имеет несколько иной подход и выглядит проще.

Предположим, что значение, сохраненное в node i, обозначается символом VALUE[i]. Моя идея состоит в том, чтобы хранить в каждой node сумму значений на пути от root до этого node. Поэтому для каждого node i, SUM[i] представляет собой сумму пути от root до node i.

Затем для каждой пары node (i,j) найдите своего общего предка k. Если SUM(i)+SUM(j)-SUM(k) = TARGET_SUM, вы нашли ответ.

Это O(n^2), поскольку мы перебираем все пары node. Хотя, мне жаль, что я не смогу найти лучший способ, чем просто собрать все пары.

Мы могли бы немного его оптимизировать, отбросив поддеревья, где value node, внедренный в поддерево, больше, чем TARGET_SUM. Любые дальнейшие оптимизации приветствуются:)

Psuedocode:

# Skipping code for storing sum of values from root to each node i in SUM[i]
for i in nodes:
    for j in nodes:
        k = common_ancestor(i,j)
        if ( SUM[i] + SUM[j] - SUM[k] == TARGET_SUM ):
            print_path(i,k,j)

Функция common_ancestor является довольно стандартной проблемой для двоичного дерева поиска. Psuedocode (из памяти, надеюсь, ошибок нет!):

sub common_ancestor (i, j):
  parent_i = parent(i)
  # Go up the parent chain until parent value is out of the range. 
  # That a red flag.
  while( VAL[i] <= VAL[parent_i] <= VAL[j] ) : 
    last_parent = parent_i
    parent_i = parent(i)
    if ( parent_i == NULL ): # root node
      break
return last_parent

Ответ 3

Старый вопрос, но здесь мой удар в нем - должно быть O (n) раз, когда вы посещаете каждый node только один раз:

  public static List<ArrayList<Integer>> pathSum(Node head, int sum) {
    List<Integer> currentPath = new ArrayList<Integer>();
    List<ArrayList<Integer>> validPaths = new ArrayList<ArrayList<Integer>>();

    dfsSum(head, sum, currentPath, validPaths);

    return validPaths;
  }

  public static void dfsSum(Node head, int sum, List<Integer> currentPath, List<ArrayList<Integer>> validPaths) {
    if (head == null) return;

    currentPath.add(head.val);

    if (head.left == null && head.right == null && sum == head.val) {
      validPaths.add(new ArrayList<Integer>(currentPath));
    }

    dfsSum(head.left, sum - head.val, new ArrayList<Integer>(currentPath), validPaths);
    dfsSum(head.right, sum - head.val, new ArrayList<Integer>(currentPath), validPaths);
  }

И класс node:

class Node {
    public int val;
    public Node left;
    public Node right;

    public Node(int val) {
      this.val = val;
    }
  }