LeetCode|LeetCode 437. Path Sum III LeetCode437.PathSumIII

题目 You are given a binary tree in which each node contains an integer value.
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 810 /\ 5-3 / \\ 3211 / \\ 3-21Return 3. The paths that sum to 8 are:1.5 -> 3 2.5 -> 2 -> 1 3. -3 -> 11

解析 【LeetCode|LeetCode 437. Path Sum III】此题和之前的一道题类似，使用递归对其进行类加。要注意的时候在每次递归的时候需要保存上一次的累加结果，这样才可以分别进行判断。如下，

newPathArr: [10] newPathArr: [15, 5] newPathArr: [18, 8, 3] // 依次类推...

代码（C）

void allPathSum(struct TreeNode* root, int sum, int* pathArr, int level, int* count); int pathSum(struct TreeNode* root, int sum) { int count = 0; allPathSum(root, sum, NULL, 1, &count); return count; }void allPathSum(struct TreeNode* root, int sum, int* pathArr, int level, int* count) { if (!root) return ; int* newPathArr = (int*)malloc(level * sizeof(int)); int i = 0; for (i = 0; i < level - 1; ++i) newPathArr[i] = pathArr[i] + root->val; newPathArr[i] = root->val; for (i = 0; i < level; ++i) { if (newPathArr[i] == sum) (*count) += 1; }allPathSum(root->left, sum, newPathArr, level + 1, count); allPathSum(root->right, sum, newPathArr, level + 1, count); free(newPathArr); }