Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
1 2 3 4 5 6 7
| 5 / 4 8 / / 11 13 4 / 7 2 1
|
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
看到这道题,嗯~
其实我锁定的本题的字眼在 “root-to-leaf”,这就是说明,至少你要从根节点一直遍历到叶节点为止。讲所有的叶节点遍历完之后,也就得到了多少个答案,然后从答案中筛选出预期的结果。
遍历的图比较好的方式一般使用递归的方式,因为迭代会使程序写法变得复杂~
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
|
class { public: void calcuSum(struct TreeNode* root, int sum) { if (nullptr != root) { if(nullptr!=root->left&&root->right==nullptr) calcuSum(root->left, sum + root->val); if(nullptr != root->right&&root->left==nullptr) calcuSum(root-&g 大专栏 求二叉树的路径和(path sum)t;right, sum + root->val); if (nullptr != root->left&&nullptr != root->right) { calcuSum(root->left, sum + root->val); calcuSum(root->right, sum + root->val); } if (nullptr == root->left&&nullptr == root->right) { calcuSum(root->left, sum + root->val); } } else { result.insert(sum); } } bool hasPathSum(TreeNode* root, int sum) { if(nullptr==root){ return false; } calcuSum(root,0); if(result.find(sum)!=result.end()){ return true; }else{ return false; } } private: set<int> result; };
|
根据鄙人的解题思路~ 写出上了以上代码~
上诉考虑到了容器的选择,我使用了set容器,主要是考虑从查找效率上。其实容器也可以选择vector,这个影响不是很大。
有了上诉题目的引子~
根据查找的结果,显示出路径来,题目如下:
Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
1 2 3 4 5 6 7 8 9 10 11 12 13
| 5 / 4 8 / / 11 13 4 / / 7 2 5 1 Return:
[ [5,4,11,2], [5,8,4,5] ]
|
这道题和上一题一样的,不同的是,我们需要记录路径了,路径怎么记录~
这时候,我们可以使用容器vector<>,然后利用形参的copy作用,讲所有root-to-leaf路径存储起来,我们只需要将上面例子的int num,换成vector就行了,然后将这个值存储起来即可~~~