Проблемы с печатью корневой папки на пути дерева для двоичного дерева

Question

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

Если пути от корня до листа являются 5-> 3-> 2-> 1, 5-> 3-> 4, 5-> 7-> 6 и 5-> 7-> 8 (пример I я использование), мой результат приходит в следующем виде:

5-> 3-> 2-> 1

5-> 3-> 2-> 14

5-> 3-> 2-> 147-> 6

5-> 3-> 2-> 147-> 68

Это из-за пути я использую StringBuilder, но я не в состоянии выяснить, что я делаю неправильно. Следующий мой код. Любая помощь была бы оценена:

public class solution{ 
    static List<String> allPaths = new ArrayList<String>(); 
    public static List<String> binaryTreePaths (BinaryTree bT){ 
     StringBuilder sb = new StringBuilder(); 
     binaryTreePathsHelper(bT, sb); 
     return allPaths; 
    } 

    public static void binaryTreePathsHelper(BinaryTree bT, StringBuilder sb){ 
     if (bT == null){ 
      return; 
     } 
     if (bT.getLeftChild() == null && bT.getRightChild() == null){ 
      sb.append(bT.getRoot() + ""); 
      allPaths.add(sb.toString()); 
      sb = new StringBuilder(); 
     } 
     else{ 
      sb.append(bT.getRoot() + "->"); 
     } 
     if (bT.getLeftChild() != null){ 
      binaryTreePathsHelper(bT.getLeftChild(), sb); 
     } 
     if (bT.getRightChild() != null){ 
      binaryTreePathsHelper(bT.getRightChild(), sb); 
     } 
    } 
} 

Answer 1

Проблема возникает, когда ваше дерево имеет два пути от текущего узла. Вы передаете тот же экземпляр StringBuilder в оба экземпляра binaryTreePathsHelper. Это означает, что оба пути заканчиваются в одном построителе строк.

Самое легкое решение - не пройти StringBuilder вокруг. Вместо этого пройдите String вокруг. Затем вы будете создавать новые String s каждый раз, когда вы присоединяетесь к вашему переданному String, исключая возможность случайного повторного использования объекта.

Если вы действительно хотите обходить экземпляры StringBuilder, вам необходимо их дублировать, когда вы рекурсивно звоните binaryTreePathsHelper. Например:

binaryTreePathsHelper(bT.getRightChild(), new StringBuilder(sb.toString());