Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

437. Sum of paths III

Given the root node of a binary tree and an integer targetSum, find the number of paths in the binary tree where the sum of the node values equals targetSum.

The path does not need to start at the root node or end at the leaf node, but the path direction must be downward (only from parent to child).

Thought analysis

Start with the simplest method, exhaustive, traversing each node, using depth-first traversal for each node to keep the number close to targetSum.

A simple DFS is very easy to build

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

Copy the code

But just using DFS once only allows us to figure out how many possibilities there are at the root, so we need to keep iterating through other nodes to get the total, which can also be done using DFS.

The second DFS is similar to the first, so we won’t repeat it here, but notice that the program still runs when the targetSum is negative, so we can pry our DFS by limiting the value of the targetSum, which greatly improves our calculation speed.