【Day 15 】2022-11-15 - 129. 求根到叶子节点数字之和

[azl397985856]

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

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/

前置知识

• DFS
• BFS
• 前序遍历

  题目描述

  
  给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

例如，从根到叶子节点路径 1->2->3 代表数字 123。

计算从根到叶子节点生成的所有数字之和。

说明: 叶子节点是指没有子节点的节点。

示例 1:

输入: [1,2,3] 1 / \ 2 3 输出: 25 解释: 从根到叶子节点路径 1->2 代表数字 12. 从根到叶子节点路径 1->3 代表数字 13. 因此，数字总和 = 12 + 13 = 25. 示例 2:

输入: [4,9,0,5,1] 4 / \ 9 0  / \ 5 1 输出: 1026 解释: 从根到叶子节点路径 4->9->5 代表数字 495. 从根到叶子节点路径 4->9->1 代表数字 491. 从根到叶子节点路径 4->0 代表数字 40. 因此，数字总和 = 495 + 491 + 40 = 1026.

[Jetery]

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

思路 DFS

• 递归三部曲:

  1. 终止条件 : 已经到达叶子节点 (左右子树为空)
  2. 返回值 : 本题不用返回, 全局变量ans加上当前cur即可
  3. 本层处理问题 : 更新cur(cur * 10 + 左/右子树的值)

     代码 (cpp)

     
     class Solution {
     public:
     int ans;
     void help(TreeNode *root, int cur) {
     if (root->left == nullptr && root->right == nullptr) {
         ans += cur;
     } else {
         if (root->left != nullptr)
             help(root->left, cur * 10 + root->left->val);
         if (root->right != nullptr)
             help(root->right, cur * 10 + root->right->val);
     }

  } int sumNumbers(TreeNode* root) { if (root == nullptr) return 0;

  help(root, root->val);
  
  return ans;

  }

};

**复杂度分析**
- 时间复杂度：O(n)
- 空间复杂度：O(height)

[mayloveless]

思路

深度优先或者广度优先遍历，遍历到子节点时，把父节点信息到带到子节点，遍历到叶节点时，即可收集到从根节点到叶节点的路径，记录数组。最后加总

代码

dfs

var sumNumbers = function(root) {
   let result = []
    if (root == null) {
        return result
    }
    let dfs = (node, path) => {
        path.push(node.val)
        if (node.left == null && node.right == null) {
            result.push([...path].join(''))
            path.pop()
            return
        }
        if (node.left != null) {
            dfs(node.left, path)
        }
        if (node.right != null) {
            dfs(node.right, path)
        }
        path.pop()
    }
    dfs(root, [], 0);

    let sum = 0;
    for(let i=0;i<result.length;i++) {
        sum += parseInt(result[i]);
    }

    return sum;
};

复杂度

时间：O(n) 每个节点访问一次 空间：O(h) 递归栈的深度即树的高度

[zhiyuanpeng]

class Solution:

    def helper(self, node, num):

        if not node.left and not node.right:
            return num*10 + node.val
        elif not node.left and node.right:
            num = num*10 + node.val
            return self.helper(node.right, num)
        elif node.left and not node.right:
            num = num*10 + node.val
            return self.helper(node.left, num)
        else:
            num = num*10 + node.val
            return self.helper(node.left, num) + self.helper(node.right, num)

    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        if not root.left and not root.right:
            return root.val
        elif not root.left and root.right:
            return self.helper(root.right, root.val)
        elif root.left and not root.right:
            return self.helper(root.left, root.val)
        else:
            return self.helper(root.left, root.val) + self.helper(root.right, root.val)

time O(N) space O(logN)

[snmyj]

class Solution {
    public int sumNumbers(TreeNode root) {
        if(root==null) return 0;
        dfs(root,root.val);
         return sum;
    }
    int sum=0;
    private void dfs(TreeNode root,int cursum){
        if(root.left==null&&root.right==null){
            sum+=cursum;
            return;
        }
        if(root.left!=null){
            dfs(root.left,cursum*10+root.left.val);
        }
        if(root.right!=null){
            dfs(root.right,cursum*10+root.right.val);
        }
    }
}

[FlipN9]

// TC: O(n), SC: O(h)
class Solution {
    int total = 0;

    public int sumNumbers(TreeNode root) {
        traverse(root, 0);
        return total;
    }

    private void traverse(TreeNode root, int curSum) {
        if (root == null) return;
        curSum = curSum * 10 + root.val;
        if (root.left == null && root.right == null) {
            total += curSum;
            return;
        }
        traverse(root.left, curSum);
        traverse(root.right, curSum);
    }
}

[Alexno1no2]

#递归左子树，回溯，递归右子树
class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        res = 0
        path = []
        def backtrace(root):
            nonlocal res
            # 空节点，返回
            if not root: return 
            path.append(root.val)
            # 叶子节点
            if not root.left and not root.right: 
                res += get_sum(path)
            # 左子树不空
            if root.left: 
                backtrace(root.left)
                path.pop()
            # 右子树不空
            if root.right: 
                backtrace(root.right)
                path.pop()

        def get_sum(arr):
            s = 0
            for i in range(len(arr)):
                s = s * 10 + arr[i]
            return s

        backtrace(root)
        return res

[Whisht]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        return self.preorderTraversal(root, 0)

    def preorderTraversal(self, root, pre_sum=0):
        if not root:
            return 0

        sum_to_cur = pre_sum * 10 + root.val # 截至到当前结点的路径和
        if not root.left and not root.right:
            return sum_to_cur

        # 若为非叶子结点，则路径和需继续累加左子结点和右子结点
        return self.preorderTraversal(root.left, sum_to_cur) + self.preorderTraversal(
            root.right, sum_to_cur
        )

复杂度

• 时间复杂度： $O(n)$
• 空间复杂度： $O(n)$

[jackgaoyuan]

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumNumbers(root *TreeNode) int {
    if root == nil {
        return 0
    }
    var dfs func(node *TreeNode)
    var path []int
    var res int
    dfs = func(node *TreeNode) {
        defer func(){
            path = path[:len(path) - 1]
        }()
        path = append(path, node.Val)
        leftNode := node.Left
        RightNode := node.Right
        if leftNode == nil && RightNode == nil {
            res += arrayToNum(path)
        }
        if leftNode != nil {
            dfs(leftNode)
        }
        if RightNode != nil {
            dfs(RightNode)
        }
    }
    dfs(root)
    return res
}

func arrayToNum(arr []int) int {
    var res int
    for i := len(arr) - 1; i >= 0; i-- {
        res += arr[i] * int(math.Pow(10, float64(len(arr) - 1 - i)))
    }
    return res
}

Time: O(n) Space: O(logn)

[MDGE]

var sumNumbers = function(root) { const dfs = (root,pre)=>{ if(!root)return 0 let cur = pre * 10 + root.val if(!root.left && !root.right){ return cur }else{ return dfs(root.left,cur) + dfs(root.right,cur) } } return dfs(root,0) };

[buer1121]

class Solution: def sumNumbers(self, root: Optional[TreeNode]) -> int: def dfs(root,cur): if not root: return 0 if not root.left and not root.right: return cur*10+root.val

        cur=cur*10+root.val

        return dfs(root.left,cur)+dfs(root.right,cur)

    return dfs(root,0)

[ringo1597]

深度优先搜索的思路

深度优先搜索是很直观的做法。从根节点开始，遍历每个节点，如果遇到叶子节点，则将叶子节点对应的数字加到数字之和。如果当前节点不是叶子节点，则计算其子节点对应的数字，然后对子节点递归遍历。

代码

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    public int dfs(TreeNode root, int prevSum) {
        if (root == null) {
            return 0;
        }
        int sum = prevSum * 10 + root.val;
        if (root.left == null && root.right == null) {
            return sum;
        } else {
            return dfs(root.left, sum) + dfs(root.right, sum);
        }
    }
}

[chiehw]

基本思路：

• 「自顶向下」求子树和，「自底向上」算节点值。

大致步骤：

1. 打表。分别讨论：空节点、叶子节点。
2. 求解下一个子树的 base 值。
3. 将左子树和右子树的值相加，作为当前节点的值。

代码：

class Solution {
private:
    int dfs(TreeNode* root, int pre){
        if(root == nullptr){
            return 0;
        }
        if(root->left == nullptr && root->right == nullptr){
            return pre*10 + root->val;
        }

        int cur = pre*10 + root->val;
        return dfs(root->left, cur) + dfs(root->right, cur);
    }
public:
    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }
};

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(h)，h为树的高度

[heng518]

class Solution { public: int sumNumbers(TreeNode* root) { return addNodes(root, 0); }

int addNodes(TreeNode* node, int num)
{
    if(node == NULL)
        return 0;
    if(!node->left && !node->right)
        return num * 10 + node->val;
    return addNodes(node->left, num * 10 + node->val) + addNodes(node->right, num * 10 + node->val);
}

};

[zywang0]

class Solution {
    private int ans;
    public int sumNumbers(TreeNode root) {
        dfs(root, 0);
        return ans;
    }

    public int dfs(TreeNode root, int n) {
        if(root.left == null && root.right == null) {
            ans += n * 10 + root.val;
            return ans;
        }
        dfs(root.left, n * 10 + root.val);
        dfs(root.right, n * 10 + root.val);
        return ans;
    }
}

[chenming-cao]

解题思路

DFS, 每走完一条路径到叶子节点则将此路径代表的数字加到res中。

代码

class Solution {
    private int res;

    public int sumNumbers(TreeNode root) {
        dfs(root, 0);
        return res;
    }

    private void dfs(TreeNode root, int last) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            res += last * 10 + root.val;
            return;
        }
        dfs(root.left, last * 10 + root.val);
        dfs(root.right, last * 10 + root.val);
    }
}

复杂度分析

• 时间复杂度：O(n)，n为树的节点数
• 空间复杂度：O(h)，h为树的高度

[gsw9818]

DFS

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs (root: Optional[TreeNode], total):
            if not root:
                return 0
            if not root.left and not root.right:
                return total * 10 + root.val
            return dfs (root.left, total * 10 + root.val) +  dfs (root.right, total * 10 + root.val)
        return dfs (root, 0)

复杂度

双ON

[yuexi001]

思路

dfs，用stack记录搜索的当前路径，当为叶子结点时，计算当前路径长度，

代码

C++ Code:

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        stack<TreeNode*> path; 
        return dfs(root, path);
    }

    int dfs(TreeNode* root, stack<TreeNode*> &path){        
        if(!root) return 0;     
        path.push(root);
        if(!root->left && !root->right){
            stack<TreeNode*> cur = path;
            path.pop();
            int sum = 0;
            int size = cur.size();
            for(int i = 0; i < size; i++){
                sum += (cur.top()->val * pow(10, i));
                cur.pop();
            }
            return sum;   
        }

        int l = dfs(root->left, path);
        int r = dfs(root->right, path);
        path.pop();

        return l + r;

    }

};

复杂度分析

• 时间复杂度：$O(n)$，n为结点数
• 空间复杂度：$O(h)$，h为树的高度

[suukii]

• Time: $O(N)$, N 为节点数
• Space: $O(H)$, H 为树的高度

/**
 * 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 {
public:
    int sumNumbers(TreeNode* root) {
        int ans = 0;
        dfs(root, 0, ans);
        return ans;
    }
private:
    void dfs(TreeNode* root, int path, int& ans) {
        if (!root) return;

        path = path * 10 + root->val;

        if (!root->left && !root->right) {
            ans += path;
            return;
        }

        dfs(root->left, path, ans);
        dfs(root->right, path, ans);
    }
};

[Alyenor]

function sumNumbers(root: TreeNode | null): number {
    let ans=0
    const dfs=(r:TreeNode, num:number)=>{
        num=num*10+r.val
        if(!r.left && !r.right) ans += num
        if(r.left) dfs(r.left,num)
        if(r.right) dfs(r.right,num)
    }
    dfs(root,0)
    return ans
};

[AtaraxyAdong]

思路

深度优先，记忆递归

递归回调条件：root.left == null && root.right == null

代码

class Solution {
    // 记录结果
    int sum = 0;

    public int sumNumbers(TreeNode root) {
        // 从根节点开始遍历，传入节点和当前值
        dfs(root, 0);
        return sum;
    }

    private void dfs(TreeNode root, int currentNum) {、
        // 终止条件
        if (root.left == null && root.right == null) {
            sum = currentNum * 10 + root.val + sum;
            return;
        }
        currentNum = currentNum * 10 + root.val;
        // 递归调用
        if (root.left != null) dfs(root.left, currentNum);
        if (root.right != null) dfs(root.right, currentNum);
    }
}

复杂度分析

• 时间复杂度：O(N)

• 空间复杂度：O(H)

  N为节点数，H为树高度

[testplm]

class Solution(object):
    def sumNumbers(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.res = 0
        self.dfs(root,0)
        return self.res

    def dfs(self,root,path):
        if root:
            if not root.left and not root.right:
                path = path*10+root.val
                self.res += path
            self.dfs(root.left,path*10+root.val)
            self.dfs(root.right,path*10+root.val)

• Time:O(n)
• Space:O(n)

[hxj2001]

思路

DFS 从根节点递归遍历整棵树，当遍历到叶节点时，将路径表示的数累加。

代码

class Solution {  
public:  
   int res = 0;  
   int sumNumbers(TreeNode* root) {  
       dfs(root, 0);  
       return res;  
   }  
   void dfs(TreeNode* root, int number)  
   {    
       number = number * 10 + root->val;  
       if(!root->left && !root->right)  res += number;    
       if(root->left)  dfs(root->left,number);            
       if(root->right) dfs(root->right,number);        
   }  
};  

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[Abby-xu]

思路

...

代码

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        p = {root: root.val}
        c = dict()
        res = 0
        while p:
            for node, number in p.items():
                if node.left:
                    c[node.left] = number*10 + node.left.val
                if node.right:
                    c[node.right] = number*10 + node.right.val
                if not node.left and not node.right:
                    res += number
            p = c
            c = dict()
        return res

复杂度

O(n)/O(n)

[testplm]

class Solution(object):
    def sumNumbers(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.res = 0
        self.dfs(root,0)
        return self.res

    def dfs(self,root,path):
        if root:
            if not root.left and not root.right:
                path = path*10+root.val
                self.res += path
            self.dfs(root.left,path*10+root.val)
            self.dfs(root.right,path*10+root.val)

• Time:O(n)
• Space:O(n)

[klspta]

    private int res = 0;

    public int sumNumbers(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        process(root, sb);
        return res;
    }

    private void process(TreeNode root, StringBuilder sb){
        if(root.left == null && root.right == null){
            sb.append(root.val);
            res += Integer.parseInt(sb.toString());
            sb.deleteCharAt(sb.length() - 1);
            return;
        }

        if(root.left != null){
            sb.append(root.val);
            process(root.left, sb);
            sb.deleteCharAt(sb.length() - 1);
        }

        if(root.right != null){
            sb.append(root.val);
            process(root.right, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

[zrtch]

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function(root) {
    if(root === null) return -1;
    const findAll = (root, path = []) => {
        if(root === null) return;
        path.push(root.val);
        if(root.left === null && root.right === null) {
            sum += parseInt(path.join(''));
        }
        root.left && findAll(root.left, path);
        root.right && findAll(root.right, path);
        path.pop();
    };
    let sum = 0;
    findAll(root);
    return sum;
};

[Serena9]

代码

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        res = 0
        q = deque()
        q.append((root,0))
        while q:
            node,value = q.popleft()
            if node.left:
                q.append((node.left,value*10+node.val))
            if node.right:
                q.append((node.right,value*10+node.val))
            if not node.left and not node.right:
                res += value*10+node.val
        return res

[sclihuiming]

思路

递归实现，每往下一层，当前数字就X10， 然后将parentNum与当前节点的val相加，最后判断如果该节点时最后一个节点，那么就将该数字加到总数上

代码

func sumNumbers(root *TreeNode) int {
    var result int
    var dfs func(node *TreeNode, parentNum int)
    dfs = func(node *TreeNode, parentNum int) {
        if node != nil {
            currentNum := parentNum + node.Val
            if node.Left == nil && node.Right == nil {
                result += currentNum
            } else {
                dfs(node.Left, currentNum*10)
                dfs(node.Right, currentNum*10)
            }
        } else {

        }
    }
    dfs(root, 0)
    return result
}

[tiandao043]

思路

递归dfs，出口一个0一个叶子节点，其余相加。

代码

class Solution {
public:
    int sumNumbers(TreeNode* root, int sum=0) {
        if(root==nullptr)return 0;
        else if(root->left==nullptr && root->right==nullptr)return sum*10+root->val;
        else{
            int a=sum*10+root->val; 
            return sumNumbers(root->left,a)+sumNumbers(root->right,a);
        }
    }
};

O(n)

[bookyue]

code

    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode root, int path) {
        if (root == null) return 0;

        path = path * 10 + root.val;
        if (root.left == null && root.right == null) return path;

        return dfs(root.left, path) + dfs(root.right, path);
    }

[xiaomingshixiaotang]

思路

1. 分析题意，根据给出示例，树的节点是类似于1->2 ,1->3这样遍历的，可以看出这是一种深度遍历
2. 采用pre dfs，先求和，再往左，最后往右，利用一个 data member 来对最后的结果进行维护

代码

/**
 * 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 {
public:
    int sumNumbers(TreeNode* root) {
        sum = 0;
        if(!root)
        {
            return 0;
        }

        pre_dfs(root,root->val);

        return sum;
    }
    void pre_dfs(TreeNode* node,int tem_sum)
    {
        if(!node->left && !node->right)
        {
            sum+=tem_sum;
            return;
        }
        if(node->left)
            pre_dfs(node->left,tem_sum * 10 + node->left->val);
        if(node->right)
            pre_dfs(node->right,tem_sum * 10 + node->right->val);
    }
private:
    int sum;
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[tzuikuo]

思路

前序遍历，回溯，遇到节点，原值*10+节点值

代码

class Solution {
public:
    int curnum=0,sum=0;
    int sumNumbers(TreeNode* root) {
        traversal(root);

        return sum;
    }
    void traversal(TreeNode* cur){
        curnum=curnum*10+cur->val;
        if(cur->left) traversal(cur->left);
        if(cur->right) traversal(cur->right);
        if(!cur->left&&!cur->right){
            sum+=curnum;
        }
        curnum=(curnum-cur->val)/10;
        return;
    }
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(1)

[AstrKing]

思路

从根节点开始，遍历每个节点，如果遇到叶子节点，则将叶子节点对应的数字加到数字之和。如果当前节点不是叶子节点，则计算其子节点对应的数字，然后对子节点递归遍历。

代码

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }

    public int dfs(TreeNode root, int prevSum) {
        if (root == null) {
            return 0;
        }
        int sum = prevSum * 10 + root.val;
        if (root.left == null && root.right == null) {
            return sum;
        } else {
            return dfs(root.left, sum) + dfs(root.right, sum);
        }
    }
}

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

[paopaohua]

思路

递归，dfs

代码

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
private int ans;
public int sumNumbers(TreeNode root) {
dfs(root,0);
return ans;       
}
public void dfs(TreeNode root,int last){

    if(root == null) return;
    if(root.left == null && root.right == null){
        ans += last * 10 + root.val;
        return;
    }
    dfs(root.left,last * 10 + root.val);
    dfs(root.right, last * 10 + root.val);
}

}

### 复杂度
- 空间：o(n)其中 n 是二叉树的节点个数。对每个节点访问一次。
- 时间：o(n)其中 n 是二叉树的节点个数。空间复杂度主要取决于递归调用的栈空间，递归栈的深度等于二叉树的高度，最坏情况下，二叉树的高度等于节点个数，空间复杂度为 O(n)

[MaylingLin]

思路

深度优先搜索，遍历每个节点然后分别对左右子节点进行递归。

代码

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(root, prevTotal):
            if not root: 
                return 0
            total = prevTotal * 10 + root.val
            if not root.left and not root.right:
                return total
            else:
                return dfs(root.left, total) + dfs(root.right, total)
        return dfs(root, 0)

复杂度

• Time: $O(n)$, n是二叉树节点个数
• Space: $O(n)$, n是二叉树节点个数

[xqmmy]

    def sumNumbers(self, root: TreeNode) -> int:
        def dfs(root: TreeNode, prevTotal: int) -> int:
            if not root:
                return 0
            total = prevTotal * 10 + root.val
            if not root.left and not root.right:
                return total
            else:
                return dfs(root.left, total) + dfs(root.right, total)

        return dfs(root, 0)

[A-pricity]

/**
 * 思路：递归
 * 遇到叶子节点返回，每层都在取值后*10
 * 左右相加
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function(root) {
    return count(root,0);
};

const count = (cur,preSum) =>{

    if(!cur) return 0;
    let sum = preSum *10 +cur.val;
    if(!cur.left && !cur.right) return sum;
    else return count (cur.left,sum) + count(cur.right, sum);
}

[GG925407590]

思路 深度优先搜索，当前值 * 2 加上 左子树的值 加上 右子树的值，递归当前操作，最后返回即可。

代码

/**
 * 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 {
public:
    int dfs(TreeNode* root, int prevSum) {
        if (root == nullptr) {
            return 0;
        }
        int sum = prevSum * 10 + root->val;
        if (root->left == nullptr && root->right == nullptr) {
            return sum;
        } else {
            return dfs(root->left, sum) + dfs(root->right, sum);
        }
    }
    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }
};

复杂度 Time: $O(n)$, n是二叉树节点个数 Space: $O(n)$, n是二叉树节点个数

[zhuzhu096]

class Solution { public: int sumNumbers(TreeNode root) { if (root == nullptr){ return 0; } dfs(root, root->val); return sum; } int sum = 0; void dfs(TreeNode root, int cursum){ if (root->left == nullptr && root->right == nullptr){ sum += cursum; return; } if (root->left != nullptr){ dfs(root->left, cursum 10 + root->left->val); } if (root->right != nullptr){ dfs(root->right, cursum 10 + root->right->val); } } };

[SJ941127]

思路

深度优先搜索 从根节点开始，遍历每个节点，如果遇到叶子节点，则将叶子节点对应的数字加到数字之和。如果当前节点不是叶子节点，对其子节点递归遍历，求其子节点对应的数据

代码

var sumNumbers = function(root) {
    return dfs(root,0)
};

const dfs = (root, preNvm) => {
    if (root == null){
       return 0;
    }
    let sum = preNvm * 10 + root.val;
    if (root.left == null && root.right == null) {
        return sum
    } else {
        return dfs(root.left,sum) + dfs(root.right,sum)
    } 
}

[RestlessBreeze]

思路

深度优先搜索

代码

class Solution {
public:
    int dfs(TreeNode* root, int prevSum) {
        if (root == nullptr) {
            return 0;
        }
        int sum = prevSum * 10 + root->val;
        if (root->left == nullptr && root->right == nullptr) {
            return sum;
        } else {
            return dfs(root->left, sum) + dfs(root->right, sum);
        }
    }
    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }
};

复杂度

时间复杂度:o(n) 空间复杂度:o(n)

[ShuqianYang]

class Solution {
    public int sumNumbers(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int sum = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();

                if (cur.left == null && cur.right == null) {
                    sum = sum + cur.val;
                }

                if (cur.left != null) {
                    cur.left.val = cur.val * 10 + cur.left.val;
                    queue.offer(cur.left);
                }

                if (cur.right != null) {
                    cur.right.val = cur.val * 10 + cur.right.val;
                    queue.offer(cur.right);
                }
            }
        }

        return sum;
    }
}

[Frederickfan]

var sumNumbers = function(root) {
   let result = []
    if (root == null) {
        return result
    }
    let dfs = (node, path) => {
        path.push(node.val)
        if (node.left == null && node.right == null) {
            result.push([...path].join(''))
            path.pop()
            return
        }
        if (node.left != null) {
            dfs(node.left, path)
        }
        if (node.right != null) {
            dfs(node.right, path)
        }
        path.pop()
    }
    dfs(root, [], 0);

    let sum = 0;
    for(let i=0;i<result.length;i++) {
        sum += parseInt(result[i]);
    }

    return sum;
};

[Alyenor]

function sumNumbers(root: TreeNode | null): number {
    let ans=0
    const dfs=(r:TreeNode, num:number)=>{
        num=num*10+r.val
        if(!r.left && !r.right) ans += num
        if(r.left) dfs(r.left,num)
        if(r.right) dfs(r.right,num)
    }
    dfs(root,0)
    return ans
};

[saitoChen]

思路

遍历使用DFS，路径借用了字符串来存储，注意遍历到叶子节点时要回溯；获得路径集后使用reduce累加即可

代码

var sumNumbers = function(root) {
    if (!root) return 0
    const result = []
    const traverse = (root, str ) => {
        if (!root) return
        str = str + String(root.val)
        // 叶子节点
        if (root && !root.left && !root.right) {
            result.push(str)
            // 回溯
            str = str.slice(0, -1)
            return
        }
        traverse(root.left, str)
        traverse(root.right, str)
    }
    traverse(root, '')

    return result.reduce((sum, cur) => {
        return sum += Number(cur)
    }, 0)
};

复杂度分析： 时间复杂度：O(N) 空间复杂度：O(N)

[wtdcai]

代码

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(root,preval):
            if root is None: return 0
            curval = preval*10 + root.val
            if root.left is None and root.right is None:
                return curval
            else:
                leftval = dfs(root.left,curval)
                rightval = dfs(root.right, curval)
                return leftval+rightval
        return dfs(root, 0)   

复杂度分析

O(n)
O(n)

[BruceZhang-utf-8]

思路

• 考虑使用dfs
• 如何确定每一个路径上的值，当前节点的值*10+左子节点的值/右子节点的值，该值需要累计，使用sum表示
• 递归的终止条件：当遇到叶子节点，此时该路径上的值可以返回，即该路径的最终值

关键点

代码

• 语言支持：Java

Java Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumNumbers(TreeNode root) {
       return nodeSum(root,0);

    }
    public int nodeSum(TreeNode node,int sum){
        if(node==null) return 0;
        sum=sum*10+node.val;
        if(node.left==null && node.right==null){
            //已经是叶子节点了，可以返回该路径的最终值了
            return sum;
        }
        return nodeSum(node.left,sum)+nodeSum(node.right,sum);
    }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[whoam-challenge]

思路

深度优先搜索

代码

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        def dfs(root: TreeNode, prevTotal: int) -> int:
            if not root:
                return 0
            total = prevTotal * 10 + root.val
            if not root.left and not root.right:
                return total
            else:
                return dfs(root.left, total) + dfs(root.right, total)

        return dfs(root, 0)

复杂度分析

-时间复杂度 O(n)，其中 n是二叉树的节点个数

-空间复杂度 O(n)

[xuanaxuan]

深度优先递归DFS

思路

• 题目求的是根到叶子节点的值，所以只要在叶子节点这一层把每条路径的值按倍数加起来并求和就行。
• 代码什么时候会跑到叶子节点呢？节点没有左子树和右子树的时候。
• 这里还需要注意函数参数root可能是null,要判空

代码

var sumNumbers = function(root) {
    return sumHelper(root, 0)
};

function sumHelper(root, sum){
    if (!root) return 0;
    const total = sum * 10 + root.val;
    if (!root.left && !root.right) {
        return total;
    } else {
        return sumHelper(root.left, total) + sumHelper(root.right, total);
    }
}

复杂度分析 时间复杂度：O(n) 空间复杂度：O(n)

BFS

思路

• 跟DFS思路一致，等到遍历到叶子节点的时候再把对应值加起来，不同的是这里把中间每一层对应的值都求出来

代码

function sumNumbers(root) {
  let sum = 0;
  let curLevel = [];
  if (root) {
    curLevel.push(root);
  }
  while (curLevel.length) {
    let nextLevel = [];
    for (let i = 0; i < curLevel.length; i++) {
      let cur = curLevel[i];
      if (cur.left) {
        cur.left.val = cur.val * 10 + cur.left.val;
        nextLevel.push(cur.left);
      }
      if (cur.right) {
        cur.right.val = cur.val * 10 + cur.right.val;
        nextLevel.push(cur.right);
      }
      if (!cur.left && !cur.right) {
        sum += cur.val;
      }
      curLevel = nextLevel;
    }
  }
  return sum;
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[aouos]

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function(root) {
  const rArr = [];

  function dfs(node, arr) {
    arr.push(node.val);
    if (!node.left && !node.right) {
      const sum = arr.join('');
      rArr.push(parseInt(sum));
      return;
    }
    if (node.left) {
      dfs(node.left, arr);
      arr.pop();
    }
    if (node.right) {
      dfs(node.right, arr);
      arr.pop();
    }
  }

  dfs(root, []);
  const ret = rArr.reduce((pre, cur) => {
    return pre += cur
  })

  return ret;
};