剑指offer
//第一种解决方法 class Solution { public: vector<vector<int> > buffer; vector<int> temp; vector<vector<int> > FindPath(TreeNode* root,int expectNumber) { if(root==NULL) return buffer; temp.push_back(root->val); if(expectNumber-root->val==0&&root->left==NULL&&root->right==NULL)//叶子结点同时之和为0 { buffer.push_back(temp); } //如果有子节点，则遍历子节点 if(root->left != nullptr) FindPath(root->left,expectNumber-root->val); if(root->right != nullptr) FindPath(root->right,expectNumber-root->val); if(temp.size()!=0) temp.pop_back();//再返回父节点之前，删除路径上的当前结点。 return buffer; } }; //第二种解决方法 class Solution { public: vector<vector<int> > buffer; vector<int> temp; int sum =0; vector<vector<int> > FindPath(TreeNode* root,int expectNumber) { if(root==NULL) return buffer; sum = sum+root->val; temp.push_back(root->val); if(expectNumber== sum &&root->left==NULL&&root->right==NULL) { buffer.push_back(temp); } //如果有子节点，则遍历子节点 if(root->left != nullptr) FindPath(root->left,expectNumber); if(root->right != nullptr) FindPath(root->right,expectNumber); if(temp.size()!=0) sum = sum-root->val; temp.pop_back();//再返回父节点之前，删除路径上的当前结点。 return buffer; } };leetcode
题目:
Given a binary tree containing digits from0-9only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path1->2->3which represents the number123.
Find the total sum of all root-to-leaf numbers.
For example,
1 / \ 2 3
The root-to-leaf path1->2represents the number12. The root-to-leaf path1->3represents the number13.
Return the sum = 12 + 13 =25.
解题的思想和上面的类似，不同之处有：
1 输出的值，
2 返回判断条件
3 返回根节点时所减去的是值，而不是和上面删除节点
4 函数开始求解的是路径之和（上面的是一个vector存储每一个节点的值。），必须定义为全部变量，不然再函数结束之后，会被释放，不能有累加的结果。
class Solution { public: int sum = 0,pathnum = 0; int sumNumbers(TreeNode *root) { if(root == nullptr) return 0; pathnum = pathnum*10+root->val; if(root->left == nullptr && root->right ==nullptr) sum+=pathnum; if(root->left !=nullptr) sumNumbers(root->left); if(root->right != nullptr) sumNumbers(root->right); if(pathnum != 0) pathnum = (pathnum-root->val)/10; return sum; } };
