LeetCode — Сумма пути II

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

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

Путь от корня к листу — это путь, начинающийся от корня и заканчивающийся любым конечным узлом. Листок — это узел без дочерних элементов.

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

Пример 1:

Input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1], targetSum = 22
Output: [[5, 4, 11, 2], [5, 8, 4, 5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

Пример 2:

Input: root = [1, 2, 3], targetSum = 5 
Output: []

Пример 3:

Input: root = [1, 2], targetSum = 0 
Output: []

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

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

Объяснение

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

Сначала проверим алгоритм.

- set 2D array vector<vector<int>> result
      1D array vector<int> current

- getPathSum(root, result, current, targetSum)

- return result

// getPathSum function
- if root == NULL
  - return

- if root->val == targetSum && root->left == NULL && root->right == NULL
  - current.push_back(root->val)
  - result.push_back(current)
  - return

- set remainingTargetSum = targetSum - root->val
- current.push_back(root->val)

- getPathSum(root->left, result, current, remainingTargetSum)
- getPathSum(root->right, result, current, remainingTargetSum)

- return

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

С++ решение

class Solution {
public:
    void getPathSum(TreeNode* root, vector<vector<int>> &result, vector<int> current, int targetSum) {
        if(root == NULL) {
            return;
        }

        if(root->val == targetSum && root->left == NULL && root->right == NULL) {
            current.push_back(root->val);
            result.push_back(current);
            return;
        }

        int remainingTargetSum = targetSum - root->val;
        current.push_back(root->val);

        getPathSum(root->left, result, current, remainingTargetSum);
        getPathSum(root->right, result, current, remainingTargetSum);

        return;
    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> result;
        vector<int> current;

        getPathSum(root, result, current, targetSum);

        return result;
    }
};

Голанг решение

func getPathSum(root *TreeNode, result *[][]int, current []int, targetSum int) {
    if root == nil {
        return
    }

    if root.Val == targetSum && root.Left == nil && root.Right == nil {
        current = append(current, root.Val)
        *result = append(*result, append([]int(nil),current...))
        return
    }

    remainingTargetSum := targetSum - root.Val

    current = append(current, root.Val)

    getPathSum(root.Left, result, current, remainingTargetSum)
    getPathSum(root.Right, result, current, remainingTargetSum)

    return
}

func pathSum(root *TreeNode, targetSum int) [][]int {
    result := [][]int{}
    current := []int{}

    getPathSum(root, &result, current, targetSum)

    return result
}

Javascript-решение

var pathSum = function(root, targetSum) {
    let result = [];

    var getPathSum = function(root, current, targetSum) {
        if(root === null) {
            return;
        }

        if(root.val === targetSum && root.left === null && root.right === null) {
            result.push([...current, root.val]);
            return;
        }

        let remainingTargetSum = targetSum - root.val;

        getPathSum(root.left, [...current, root.val], remainingTargetSum);
        getPathSum(root.right, [...current, root.val], remainingTargetSum);

        return;
    }

    getPathSum(root, [], targetSum);

    return result;
};

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

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

Step 1: initialize vector<vector<int>> result;
        vector<int> current;

Step 2: getPathSum(root, result, current, targetSum)
        getPathSum(root, [[]], [], 22)
        the root is at 5

// getPathSum
Step 3: if root == NULL
          false

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

           remainingTargetSum = targetSum - root->val
                              = 22 - 5
                              = 17

           current.push_back(root->val)
           current = [5]

           getPathSum(root->left, result, current, remainingTargetSum)
           getPathSum(4, [[]], [5], 17)

Step 4: if root == NULL
          the root is at 4
          false

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

           remainingTargetSum = targetSum - root->val
                              = 17 - 4
                              = 13

           current.push_back(root->val)
           current = [5, 4]

           getPathSum(root->left, result, current, remainingTargetSum)
           getPathSum(11, [[]], [5, 4], 13)

Step 5: if root == NULL
          the root is at 11
          false

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

           remainingTargetSum = targetSum - root->val
                              = 13 - 11
                              = 2

           current.push_back(root->val)
           current = [5, 4, 11]

           getPathSum(root->left, result, current, remainingTargetSum)
           getPathSum(7, [[]], [5, 4, 11], 2)

Step 6: if root == NULL
          the root is at 7
          false

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

           remainingTargetSum = targetSum - root->val
                              = 2 - 7
                              = -5

           current.push_back(root->val)
           current = [5, 4, 11, 7]

           getPathSum(root->left, result, current, remainingTargetSum)
           getPathSum(NULL, [[]], [5, 4, 11, 7], -5)

Step 7: if root == NULL
          the root is NULL
          true

          We backtrack to step 6 and continue

Step 8: getPathSum(root->right, result, current, remainingTargetSum)
        getPathSum(2, [[]], [5, 4, 11], 2)

Step 9: if root == NULL
          the root is at 2
          false

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

           current.push_back(root->val)
           current = [5, 4, 11, 2]

           result.push_back(current)
           result = [[5, 4, 11, 2]]

           return

        We backtrack to step 4 and continue

Step 10: getPathSum(root->right, result, current, remainingTargetSum)
         getPathSum(NULL, [[5, 4, 11, 2]], [5, 4], 13)

Step 11: if root == NULL
          the root is NULL
          true

          We backtrack to step 3 and continue

Step 12: getPathSum(root->right, result, current, remainingTargetSum)
         getPathSum(8, [[5, 4, 11, 2]], [5], 17)

Step 13: if root == NULL
          the root is at 8
          false

         if root->val == targetSum && root->left == NULL && root->right == NULL
            8 == 17
            false

         remainingTargetSum = targetSum - root->val
                              = 17 - 8
                              = 9

         current.push_back(root->val)
         current = [5, 8]

         getPathSum(root->left, result, current, remainingTargetSum)
         getPathSum(13, [[5, 4, 11, 2]], [5, 8], 9)

Step 14: if root == NULL
          the root is at 13
          false

         if root->val == targetSum && root->left == NULL && root->right == NULL
            13 == 9
            false

         remainingTargetSum = targetSum - root->val
                              = 9 - 13
                              = -4

         current.push_back(root->val)
         current = [5, 8, 13]

         getPathSum(root->left, result, current, remainingTargetSum)
         getPathSum(NULL, [[5, 4, 11, 2]], [5, 8, 13], -4)

Step 15: if root == NULL
          the root is NULL
          true

          We backtrack to step 14 and continue

Step 16: getPathSum(root->right, result, current, remainingTargetSum)
         getPathSum(NULL, [[5, 4, 11, 2]], [5, 8, 13], -4)

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

          We backtrack to step 13 and continue

Step 18: getPathSum(root->right, result, current, remainingTargetSum)
         getPathSum(4, [[5, 4, 11, 2]], [5, 8], 9)

Step 19: if root == NULL
          the root is at 4
          false

         if root->val == targetSum && root->left == NULL && root->right == NULL
            4 == 9
            false

         remainingTargetSum = targetSum - root->val
                              = 9 - 4
                              = 5

         current.push_back(root->val)
         current = [5, 8, 4]

         getPathSum(root->left, result, current, remainingTargetSum)
         getPathSum(5, [[5, 4, 11, 2]], [5, 8, 4], 5)

Step 20: if root == NULL
          the root is at 5
          false

         if root->val == targetSum && root->left == NULL && root->right == NULL
            5 == 5
            true

            current.push_back(root->val)
            current = [5, 8, 4, 5]

            result.push_back(current)
            result = [[5, 4, 11, 2], [5, 8, 4, 5]]

            return

        We backtrack to step 19 and continue

Once the last rightmost lead node is processed
we return the result

The answer is [[5, 4, 11, 2], [5, 8, 4, 5]].

Первоначально опубликовано на https://alkeshghorpade.me.

Если этот пост был полезен, пожалуйста, несколько раз нажмите кнопку аплодисментов 👏, чтобы выразить свою поддержку автору 👇

🚀Разработчики: учитесь и развивайтесь, не отставая от того, что важно, ПРИСОЕДИНЯЙТЕСЬ К FAUN.

смотрите также:

Новые материалы

Как проанализировать работу вашего классификатора?

Не всегда просто знать, какие показатели использовать С развитием глубокого обучения все больше и больше людей учатся обучать свой первый классификатор. Но как только вы закончите..

Работа с цепями Маркова, часть 4 (Машинное обучение)

Нелинейные цепи Маркова с агрегатором и их приложения (arXiv) Автор : Бар Лайт Аннотация: Изучаются свойства подкласса случайных процессов, называемых дискретными нелинейными цепями Маркова..

Crazy Laravel Livewire упростил мне создание электронной коммерции (панель администратора и API) [Часть 3]

Как вы сегодня, ребята? В этой части мы создадим CRUD для данных о продукте. Думаю, в этой части я не буду слишком много делиться теорией, но чаще буду делиться своим кодом. Потому что..

Использование машинного обучения и Python для классификации 1000 сезонов новичков MLB Hitter

Чему может научиться машина, глядя на сезоны новичков 1000 игроков MLB? Это то, что исследует это приложение. В этом процессе мы будем использовать неконтролируемое обучение, чтобы..

Учебные заметки: создание моего первого пакета Node.js

Это мои обучающие заметки, когда я научился создавать свой самый первый пакет Node.js, распространяемый через npm. Оглавление Глоссарий I. Новый пакет 1.1 советы по инициализации..

Забудьте о Matplotlib: улучшите визуализацию данных с помощью умопомрачительных функций Seaborn!

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

ИИ в аэрокосмической отрасли

Каждый полет – это шаг вперед к великой мечте. Чтобы это происходило в их собственном темпе, необходима команда астронавтов для погони за космосом и команда технического обслуживания..

Метки

Machine Learning JavaScript Data Science Artificial Intelligence Software Development Python Web Development Coding Deep Learning AI React Software Engineering Nodejs Java Front End Development Typescript Computer Science Data Algorithms Development NLP Tech Programming Languages CSS ChatGPT HTML Python Programming Javascript Tips Angular Computer Vision Data Visualization Neural Networks Startup Tutorial Statistics Productivity Reactjs Learning