二叉树根到叶子节点的所有路径的和

题目描述

给定一个仅包含数字\ 0-9 0−9 的二叉树，每一条从根节点到叶子节点的路径都可以用一个数字表示。
例如根节点到叶子节点的一条路径是1\to 2\to 31→2→3,那么这条路径就用\ 123 123 来代替。
找出根节点到叶子节点的所有路径表示的数字之和
例如：

这颗二叉树一共有两条路径，
根节点到叶子节点的路径 1\to 21→2 用数字\ 12 12 代替
根节点到叶子节点的路径 1\to 31→3 用数字\ 13 13 代替
所以答案为\ 12+13=25 12+13=25

示例1

输入

复制

{1,0}

返回值

复制

10

示例2

输入

复制

{1,#,9}

返回值

复制

19

DFS

import java.util.*;
public class Solution {
    public int sumNumbers (TreeNode root) {
        dfs(root,0);
        return res;
    }
    
    int res = 0;
    public void dfs(TreeNode root,int val){
        if(root==null) return;
        int sum = val*10+root.val;
        if(root.left!=null)dfs(root.left,sum);
        if(root.right!=null)dfs(root.right,sum);
        // 当左右子树都为空的时候再去计算和，否则会重复计算和
        if(root.left==null&&root.right==null){
            res += sum;
            return;
        }
    }
}

赏

谢谢你请我吃糖果

微信