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

原题链接
image.png

思路

  • pre_sum代表之前改路径上所有数字的和
  • dfs(root, pre_sum)代表以root为根节点的子树的所有数字之和

  • dfs(当前节点) = (pre_sum * 10 + dfs(右子树)) + (pre_sum * 10 + dfs(左子树))

    代码

    1. /**
    2. * Definition for a binary tree node.
    3. * struct TreeNode {
    4. *     int val;
    5. *     TreeNode *left;
    6. *     TreeNode *right;
    7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10. * };
    11. */
    12. class Solution {
    13. public:
    14.   int sumNumbers(TreeNode* root) {
    15.       return dfs(root, 0);
    16.   }
    18.   int dfs(TreeNode* root, int pre_sum) {
    19.       if (!root) {
    20.           return 0;
    21.       }
    23.       // 如果是叶子节点
    24.       int ans = 0;
    25.       if (!root->left && !root->right) {
    26.           return pre_sum * 10 + root->val;
    27.       } 
    28.       if (root->left) {
    29.           int cur_sum = pre_sum * 10 + root->val;
    30.           ans += dfs(root->left, cur_sum);
    31.       }
    32.       if (root->right) { 
    33.           int cur_sum = pre_sum * 10 + root->val;
    34.           ans += dfs(root->right, cur_sum);
    35.       }
    37.       return ans;
    38.   }
    39. };