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

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

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

Путь не обязательно должен начинаться или заканчиваться в корне или листе, но он должен идти вниз (т. е. проходить только от родительских узлов к дочерним узлам).

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

Пример 1:

Input: root = [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

Пример 2:

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

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

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

Объяснение

Рекурсия

Проблема аналогична нашим предыдущим сообщениям в блоге Сумма пути и Сумма пути II.

Нам нужно изменить алгоритм для подсчета различных путей в дереве. Мы будем использовать алгоритм DFS для подсчета путей. Проверим алгоритм.

// pathSum method
- if root == null
  - return 0
- return dfs(root, 0, targetSum) +
    pathSum(root->left, targetSum) +
    pathSum(root->right, targetSum)
// dfs method
- if root == null
  - return 0
- set currentSum = previousSum + root->val
      count = 0
- if currentSum == targetSum
  - count = 1
- return count +
    dfs(root->left, currentSum, targetSum) +
    dfs(root->right, currentSum, targetSum)

Временная сложность может быть уменьшена до O(nlog(n)) путем обращения связанного списка.

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

С++ решение

class Solution {
public:
    int dfs(TreeNode* root, long long previousSum, long long targetSum) {
        if(root == NULL) {
            return 0;
        }
  
        int currentSum = previousSum + root->val;
        int count = 0;
  
        if(currentSum == targetSum) {
            count = 1;
        }

        return count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum);
    }

    int pathSum(TreeNode* root, int targetSum) {
        if(root == NULL) {
            return 0;
        }
        return dfs(root, 0, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum);
    }
};

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

func dfs(root *TreeNode, previousSum, targetSum int) int {
    if root == nil {
        return 0
    }
    
    currentSum := previousSum + root.Val
    count := 0
    
    if currentSum == targetSum {
        count = 1
    }

    return count + dfs(root.Left, currentSum, targetSum) + dfs(root.Right, currentSum, targetSum)
}

func pathSum(root *TreeNode, targetSum int) int {
    if root == nil {
        return 0
    }
    return dfs(root, 0, targetSum) + pathSum(root.Left, targetSum) + pathSum(root.Right, targetSum)
}

Javascript-решение

var dfs = function(root, previousSum, targetSum) {
    if(root == null) {
        return 0;
    }

    let currentSum = previousSum + root.val;
    let count = 0;
    
    if(currentSum == targetSum) {
        count = 1;
    }

    return count + dfs(root.left, currentSum, targetSum) + dfs(root.right, currentSum, targetSum);
};

var pathSum = function(root, targetSum) {
    if(root == null) {
        return 0;
    }
    return dfs(root, 0, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
};

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

Input: root = [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1]
       targetSum = 8
// pathSum method
Step 1: if root == NULL
          root -> 10
          false
Step 2: dfs(root, 0, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum)
        dfs(->10, 0, 8) + pathSum(->5, 8) + pathSum(-3, 8)
// dfs method
Step 3: if root == NULL
          root -> 10
          false
          currentSum = previousSum + root->val
                     = 0 + 10
                     = 10
          count = 0
          currentSum == targetSum
          10 == 8
          false
          count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
          0 + dfs(->5, 10, 8) + dfs(->(-3), 10, 8)
// dfs(->5, 10, 8)
Step 4: if root == NULL
          root -> 5
          false
          currentSum = previousSum + root->val
                     = 10 + 5
                     = 15
          count = 0
          currentSum == targetSum
          15 == 8
          false
          count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
          0 + dfs(->3, 15, 8) + dfs(2, 15, 8)
// dfs(->3, 15, 8)
Step 5: if root == NULL
          root -> 3
          false
          currentSum = previousSum + root->val
                     = 15 + 3
                     = 18
          count = 0
          currentSum == targetSum
          18 == 8
          false
          count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
          0 + dfs(->3, 18, 8) + dfs(->(-2), 18, 8)
// dfs(->3, 18, 8)
Step 6: if root == NULL
          root -> 3
          false
          currentSum = previousSum + root->val
                     = 18 + 3
                     = 21
          count = 0
          currentSum == targetSum
          21 == 8
          false
          count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
          0 + dfs(->nil, 21, 8) + dfs(->nil, 21, 8)
         Both dfs(->nil, 21, 8), dfs(->nil, 21, 8) node is nil so we return 0 and backtrack to Step 5
         0 + dfs(->3, 18, 8) + dfs(->(-2), 18, 8) where we solve for
         dfs(->(-2), 18, 8)
// dfs(->(-2), 18, 8)
Step 7: if root == NULL
          root -> -2
          false
          currentSum = previousSum + root->val
                     = 21 + -2
                     = 19
          count = 0
          currentSum == targetSum
          19 == 8
          false
          count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
          0 + dfs(->nil, 19, 8) + dfs(->nil, 19, 8)
          Both dfs(->nil, 19, 8), dfs(->nil, 19, 8) node is nil so we return 0 and backtrack to Step 4
          0 + dfs(->3, 15, 8) + dfs(2, 15, 8) where we solve for
          dfs(2, 15, 8)
// dfs(2, 15, 8)
Step 8: if root == NULL
          root -> 2
          false
          currentSum = previousSum + root->val
                     = 15 + 2
                     = 17
          count = 0
          currentSum == targetSum
          17 == 8
          false
          count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
          0 + dfs(->nil, 17, 8) + dfs(1, 17, 8)
          dfs(->nil, 17, 8) returns 0 as node is nil, so we evaluate for
          dfs(1, 17, 8)
// dfs(1, 17, 8)
Step 9: if root == NULL
          root -> 1
          false
          currentSum = previousSum + root->val
                     = 17 + 1
                     = 18
          count = 0
          currentSum == targetSum
          18 == 8
          false
          count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
          0 + dfs(->nil, 18, 8) + dfs(->nil, 18, 8)
          Both dfs(->nil, 19, 8), dfs(->nil, 19, 8) node is nil so we return 0 and backtrack to Step 3
          0 + dfs(->5, 10, 8) + dfs(->(-3), 10, 8) where we solve for
          dfs(->(-3), 10, 8)
// dfs(->(-3), 10, 8)
Step 10: if root == NULL
          root -> -3
          false
          currentSum = previousSum + root->val
                     = 10 + -3
                     = 7
          count = 0
          currentSum == targetSum
          7 == 8
          false
          count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
          0 + dfs(->nil, 7, 8) + dfs(->11, 7, 8)
          dfs(->nil, 7, 8) returns 0 as node is nil, so we evaluate for
          dfs(->11, 7, 8)
// dfs(->11, 7, 8)
Step 11: if root == NULL
          root -> 11
          false
          currentSum = previousSum + root->val
                     = 7 + 11
                     = 18
          count = 0
          currentSum == targetSum
          18 == 8
          false
          count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
          0 + dfs(->nil, 18, 8) + dfs(->nil, 18, 8)
          Both dfs(->nil, 18, 8), dfs(->nil, 18, 8) node is nil so we return 0 and backtrack to Step 2
          dfs(->10, 0, 8) + pathSum(->5, 8) + pathSum(-3, 8)
          where we have dfs(->10, 0, 8) as 0
          and we evaluate for pathSum(->5, 8)
// pathSum(->5, 8)
Step 12: if root == NULL
          root -> 5
          false
          dfs(root, 0, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum)
          dfs(->5, 0, 8) + pathSum(->3, 8) + pathSum(->2, 8)
// dfs(->5, 0, 8)
Step 13: if root == NULL
          root -> 5
          false
          currentSum = previousSum + root->val
                     = 0 + 5
                     = 5
          count = 0
          currentSum == targetSum
          5 == 8
          false
          count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
          0 + dfs(->3, 5, 8) + dfs(->2, 5, 8)
// dfs(->3, 5, 8)
Step 14: if root == NULL
           root -> 3
           false
           currentSum = previousSum + root->val
                      = 5 + 3
                      = 8
           count = 0
           currentSum == targetSum
           8 == 8
           true
           count = 1
           count + dfs(root->left, currentSum, targetSum) + dfs(root->right, currentSum, targetSum)
           1 + dfs(->3, 8, 8) + dfs(->(-2), 8, 8)
We similarly iterate over the rest of the tree and return the count.

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