leetcode 129. 求根节点到叶节点数字之和

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:vector<int> path;int ans;//将保存的路径值转化为数字int path2sum(vector<int>& path){int sum = 0;for(int i=0; i<path.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;}
};