Блог

Я пытаюсь решить проблему с суммой пути, используя рекурсию в Leetcode. Я не умею решать вопросы с помощью рекурсии. Я видел некоторые другие решения, но пытался реализовать их самостоятельно. Я не понимаю, что я делаю неправильно в своем подходе. Если кто-нибудь поможет мне понять, где я делаю неправильно, я был бы очень признателен за вашу помощь. Заранее спасибо.

Постановка задачи: учитывая корень двоичного дерева и целочисленную целевую сумму, верните true, если дерево имеет путь от корня к листу, так что сложение всех значений вдоль пути равно целевой сумме.

Лист — это узел без дочерних элементов.

 class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(checkSum(root, targetSum) == 1) return true;
        return false;
    }
    
    public int checkSum(TreeNode root, int targetSum){
        if(root == null) return 0;
        if(root.left != null){
           // Assuming my checkSum() function already works, I want to get the left tree sum
            int left = checkSum(root.left, targetSum-root.val);
            // Adding the root value to the left tree sum to check if it equals to targetSum
            // If it matches, it returns 1
            if(left root.val == targetSum){
                return 1;
            };
        }
        if(root.right != null){
           // Assuming my checkSum() function already works, I want to get the right tree sum
            int right = checkSum(root.right, targetSum-root.val);
            // Adding the root value to the right tree sum to check if it equals to targetSum
            // If it matches, it returns 1
            if(right root.val == targetSum){
                return 1;
            };
        }
        // When everything above, does not match, it returns 0
        return 0;
    }
}
 

Мой подход:
Я читал во время изучения рекурсии, что вы должны верить, что ваша функция работает. Поэтому, полагая, что я предполагаю, что вызов контрольной суммы (root.left, targetSum — root.val) должен возвращать сумму левого поддерева. После этого я добавляю root.val к левой сумме и проверяю, равно ли оно целевой сумме. Я сделал то же самое и для правильного поддерева. Моя функция в настоящее время выдает неверный вывод. Может кто-нибудь помочь мне понять, где я ошибаюсь с примерами. Заранее спасибо за вашу помощь.

Ключевая проблема с вашим кодом заключается в том, что вы фактически не рассмотрели базовый сценарий. Согласно вашему коду, когда мы достигли листа, мы просто возвращаем 0. Вы вообще не принимаете во внимание targetSum переменную. Подумайте об этом. Представьте себе очень простой случай, в котором у вас есть корень с двумя дочерними элементами, значения которых равны 10, 5, 20 соответственно и targetSum = 30 . Ответ на этот ввод должен быть true , но ваша функция вернет false, потому что она просто игнорирует значение targetSum в нижней части стека (другими словами, базовый вариант).

Итак, проверка базового варианта может выглядеть так:

 if (root.left == null amp;amp; root.right == null) {
    //some logic 
}
 

Aprat из базовой проверки,
if-операторы

 if(left root.val == targetSum){
   return 1;
};
if(right root.val == targetSum){
   return 1;
};
 

неверны, поскольку вы left/right являетесь результатом контрольной суммы, которая возвращает только 1 или 0. Нет смысла добавлять его root.val , поскольку это не означает сумму на пути к некоторому листу. Я бы заменил первый оператор if на

 if (left == 1) {
    return 1;
} 
 

То же самое следует сделать со вторым if-оператором.
Я надеюсь, что это поможет вам.