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

Question

Учитывая двоичное дерево поиска и целевое значение, найдите все пути (если существует более одного), которые суммируют до целевого значения. Это может быть любой путь в дереве. Это не должно быть от корня.

Например, в следующем дереве двоичного поиска:

  2
 / \ 
1   3 

когда сумма должна быть 6, путь 1 -> 2 -> 3 должен быть напечатан.

Answer 1

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

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

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

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

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

Answer 2

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

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

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

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

Мы могли бы немного оптимизировать его, отбрасывая поддеревья, где value узла, корни которого в поддереве, больше 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's value is out of the range. 
  # That's 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

Answer 3

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

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

И класс узла:

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

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