详细注释,简单易懂的DFS解法。
class Solution {
public:
int res, sum; //res存总和,sum存每条叶子节点路劲的和
void dfs(TreeNode* root)
{
sum = sum * 10 + root->val; //先把当前节点的值加上
if (!root->left && !root->right) //若该节点已经是叶子节点
res += sum; //将该路径和加入总和
if (root->left) dfs(root->left); //递归左右子节点(如果有的话)
if (root->right) dfs(root->right);
sum = (sum - root->val) / 10; //恢复现场
}
int sumNumbers(TreeNode* root) {
dfs(root);
return res;
}
};