以就业为导向的高职计算机专业网站设计,福州做网站外包团队,邢台哪儿做wap网站,天津网站建设制作开发公司2023.9.8 好久没写回溯题了#xff0c;有点陌生ToT。 本题思路就是通过回溯保存所有根节点到叶子节点的路径#xff0c;然后将这些路径转化为数字并全部相加。 直接看代码#xff1a;
/*** Definition for a binary tree node.* struct TreeNode {* int val;* Tre…2023.9.8 好久没写回溯题了有点陌生ToT。 本题思路就是通过回溯保存所有根节点到叶子节点的路径然后将这些路径转化为数字并全部相加。 直接看代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
private:vectorint path;int ans;//将保存的路径值转化为数字int path2sum(vectorint path){int sum 0;for(int i0; ipath.size(); i){sum sum * 10 path[i];}return sum;}//回溯void backtrating(TreeNode* cur){//终止条件遇到了叶子节点if(!cur-left !cur-right){ans path2sum(path);return;}if(cur-left){path.push_back(cur-left-val);backtrating(cur-left);path.pop_back();}if(cur-right){path.push_back(cur-right-val);backtrating(cur-right);path.pop_back();}}
public:int sumNumbers(TreeNode* root) {path.push_back(root-val);backtrating(root);return ans;}
};
