原题地址（中等）

方法1—深搜

思路

虽然这题是中等，但是很简单，就是普通的递归深搜，5分钟就做完了。

当然了，也可以用广度优先遍历来做，需要用栈/队列来模拟，不过代码不如递归简洁，没必要了。

代码

  1. class Solution {
  2. public:
  3.     int sumNumbers(TreeNode* root) {
  4.         return calSum(root, 0);
  5.     }
  7.     int calSum(TreeNode* root, int sum) {
  8.         if(!root)   return 0;
  9.         sum = sum*10 + root->val;
  10.         if(!root->left && !root->right){
  11.             return sum;
  12.         }
  13.         return calSum(root->left, sum) + calSum(root->right, sum);
  14.     }
  15. };
class Solution {
public:
    int ans;
    int sumNumbers(TreeNode* root) {
        if(!root)   return 0;
        calSum(root, root->val);
        return ans;
    }

    void calSum(TreeNode* root, int sum){
        if(root && !root->left && !root->right){
            ans += sum;
            return;
        }

        if(root->left)  calSum(root->left, sum*10+root->left->val);
        if(root->right) calSum(root->right, sum*10+root->right->val);
    }
};

时空复杂度

空间复杂度O(N)（最坏情况下） 时间复杂度O(N)