LeetCode — Path Sum - Ответы

Содержание

Постановка задачи
Объяснение
Рекурсия
Решение на C++
Решение на Golang
Решение для Javascript

Постановка задачи

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

Лист — это узел, не имеющий детей.

Постановка задачи взята с сайта: https://leetcode.com/problems/path-sum

Пример 1:

Input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

Вход в полноэкранный режим Выход из полноэкранного режима

Пример 2:

Input: root = [1, 2, 3], targetSum = 5
Output: false
Explanation: There are two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with a sum = 5.

Вход в полноэкранный режим Выход из полноэкранного режима

Пример 3:

Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.

Войти в полноэкранный режим Выход из полноэкранного режима

Ограничения:

- The number of nodes in the tree is in the range [0, 5000].
- -1000 <= Node.val <= 1000
- -1000 <= targetSum <= 1000

Войти в полноэкранный режим Выйти из полноэкранного режима

Объяснение

Рекурсия

Для решения большинства проблем, связанных с деревьями, лучше всего использовать рекурсию или очереди/стеки.

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

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

Давайте сначала проверим алгоритм.

- if root == null
  - return false

- if root->val == targetSum && root->left == null && root->right == null
  - return true

- remainingTarget = targetSum - root->val

- return hasPathSum(root->left, remainingTarget) || hasPathSum(root->right, remainingTarget)

Вход в полноэкранный режим Выход из полноэкранного режима

Давайте проверим наш алгоритм на C++, Golang и Javascript.

Решение на C++

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == NULL) {
          return false;
        }

        if(root->val == targetSum && root->left == NULL && root->right == NULL) {
            return true;
        }

        int remainingTarget = targetSum - root->val;

        return hasPathSum(root->left, remainingTarget) || hasPathSum(root->right, remainingTarget);
    }
};

Вход в полноэкранный режим Выход из полноэкранного режима

Решение на Golang

func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }

    if root.Val == targetSum && root.Left == nil && root.Right == nil {
        return true
    }

    remainingTargetSum := targetSum - root.Val

    return hasPathSum(root.Left, remainingTargetSum) || hasPathSum(root.Right, remainingTargetSum)
}

Войти в полноэкранный режим Выход из полноэкранного режима

Решение для Javascript

var hasPathSum = function(root, targetSum) {
    if(root == null) {
        return false;
    }

    if(root.val == targetSum && root.left == null && root.right == null) {
        return true;
    }

    let remainingTarget = targetSum - root.val;

    return hasPathSum(root.left, remainingTarget) || hasPathSum(root.right, remainingTarget);
};

Войти в полноэкранный режим Выход из полноэкранного режима

Давайте проверим наш алгоритм для примера 1.

Input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1]
       targetSum = 22

Step 1: if root == null
           the root is at 5
           false

Step 2: if root->val == targetSum && root->left == NULL && root->right == NULL
           5 == 22
           false

Step 3: remainingTarget = targetSum - root->val
                        = 22 - 5
                        = 17

Step 4: return hasPathSum(root->left, remainingTarget) ||
                 hasPathSum(root->right, remainingTarget)

        root->left = 4
        root->right = 8
        remainingTarget = 17

Step 5: if root == null
           the root is at 4
           false

Step 6: if root->val == targetSum && root->left == NULL && root->right == NULL
           4 == 17
           false

Step 7: remainingTarget = targetSum - root->val
                        = 17 - 4
                        = 13

Step 8: return hasPathSum(root->left, remainingTarget) ||
                 hasPathSum(root->right, remainingTarget)

        root->left = 11
        root->right = nil
        remainingTarget = 13

Step 9: if root == null
           the root is at 11
           false

Step 10: if root->val == targetSum && root->left == NULL && root->right == NULL
           11 == 13
           false

Step 11: remainingTarget = targetSum - root->val
                        = 13 - 11
                        = 2

Step 12: return hasPathSum(root->left, remainingTarget) ||
                 hasPathSum(root->right, remainingTarget)

        root->left = 7
        root->right = 2
        remainingTarget = 2

Step 13: if root == null
           the root is at 7
           false

Step 14: if root->val == targetSum && root->left == NULL && root->right == NULL
           7 == 2
           false

Step 15: remainingTarget = targetSum - root->val
                         = 2 - 7
                         = -5

Step 16: return hasPathSum(root->left, remainingTarget) ||
                 hasPathSum(root->right, remainingTarget)

        root->left = null
        root->right = null
        remainingTarget = -5

Step 17: if root == null
            the root is null
            true

          We backtrack to Step 16

Step 18: if root == null
            the root is null
            true

          We backtrack to Step 12

Step 19: if root == null
           the root is at 2
           false

Step 20: if root->val == targetSum && root->left == NULL && root->right == NULL
           2 == 2
           true

We return true here and backtrack for the rest of the tree. In the end, we have OR condition and have found the path once we return the answer as true.

Вход в полноэкранный режим Выход из полноэкранного режима