How to Count the Path Sum from a Binary Tree using Depth First S
- 时间:2020-09-23 15:11:59
- 分类:网络文摘
- 阅读:87 次
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 = 8
10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1Return 3. The paths that sum to 8 are:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
Compute the Path Sum in Binary Tree using DFS Algorithm
The binary tree problems are most likely to be solved using recursion, which we will implement a Depth First Search algorithm to go through all the nodes.
As the path sum does not begin from the root, hence, the total path sum would be the following equation:
1 | F(root, sum) = F(root>left, sum) + F(root>right, sum) + G(root, sum) |
F(root, sum) = F(root>left, sum) + F(root>right, sum) + G(root, sum)
Where G is a function to compute the path sum from the exactly the root.
We can deduct the current node value from the sum and pass it down to the tree, until the remainder of the sum is exactly the current node’s value, when we increment the answer by one.
The following is the C++ implementation that counts the path sum given a root using the Depth First Search Algorithm.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int pathSum(TreeNode* root, int sum) { if (root == nullptr) return 0; return pathFromRoot(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum); } int pathFromRoot(TreeNode* root, int sum) { if (root == nullptr) return 0; int r1 = pathFromRoot(root->left, sum - root->val); int r2 = pathFromRoot(root->right, sum - root->val); int ans = (root->val == sum) ? 1 : 0; return ans + r1 + r2; } }; |
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int pathSum(TreeNode* root, int sum) { if (root == nullptr) return 0; return pathFromRoot(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum); } int pathFromRoot(TreeNode* root, int sum) { if (root == nullptr) return 0; int r1 = pathFromRoot(root->left, sum - root->val); int r2 = pathFromRoot(root->right, sum - root->val); int ans = (root->val == sum) ? 1 : 0; return ans + r1 + r2; } };
The space complexity is O(N) and the time complexity is O(N^2) and the best case is O(NlogN).
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:醉后清醒又一日 看《喜羊羊与灰太狼》的感想 过六一作文350字 弘扬长征精神 学唱歌作文500字 独特的美作文400字 集市之旅 写人作文新数学老师作文400字 我的寒假生活作文700字 家乡的云作文
- 评论列表
-
- 添加评论