как искать сумму чисел в двоичном дереве?

Question

Мне нужно найти любую комбинацию чисел в BinaryTree, которая даст мне сумму, которую я ищу. Например, для дерева, имеющего номера: 9,1,6,3,2,5, если система получит сумму 18, она вернет строку «9,1,3,5». Как я могу это сделать, пожалуйста.

Комбинация должны начинаться с корня и вниз в Тропы & метод должны работать в с возвратами рекурсии

код, который я написал это:

public String path(int sum) 
    { 
     return path(sum, root); 
    } 
    private String path(int sum, Node t) 
    { 
     if (t == null) 
      return ""; 

     sum = sum - t.getNumber(); 

     if (sum == 0) 
      return t.getNumber() + ", "; 


     return path(sum, t.getLeftSon()) + path(sum, t.getRightSon()); 

    } 

Answer 1

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

1. Base Case, что проблема может в конечном итоге достичь путем разделяй и властвуй подход
2. Общий случай, который используется, чтобы разделить проблему в меньшие части до достижения базовый чехол желаемый.
   

---

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

Если, что дерево достигает листа, а сумма не найдена, то этого не существует в этом поддереве.
return "";

еще если сумма будет найден в поддереве.
return t.getNumber() + ", ";

еще мы еще не достигли суммы, и есть еще несколько узлов для детей.
path(t.getleftSon()); path(t.getRightSon()); return t.getNumber() + ", "

Я не проверял этот точный код в IDE, но логика должна быть правильной