「力扣」第 129 题：求根到叶子结点数字之和

递归 二叉树
专题 12：树
发布日期:   2017-12-03

「力扣」第 129 题：求根到叶子结点数字之和

给定一个二叉树，它的每个结点都存放一个 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.

要求：给定一棵二叉树，每个结点只包含数字 0-9，从根结点到叶子结点的每条路径可以表示成一个数，求这些数的和。

Java 代码1：使用 path，递归回溯的常规解法。

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

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

// 我的思路：使用深度优先遍历，遍历到根结点的时候，把数字加一加
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {

    private List<String> result = new ArrayList<>();

    private void sumNumbers(TreeNode node, String path) {
        if (node == null) {
            return;
        }

        path = path + node.val;
        if (node.left == null && node.right == null) {
            // 才是叶子结点，执行我们的逻辑
            result.add(path);
            return;
        }
        sumNumbers(node.left, path);
        sumNumbers(node.right, path);
    }

    private int convert() {
        int sum = 0;
        for (String s : result) {
            sum += Integer.parseInt(s);
        }
        return sum;
    }

    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        sumNumbers(root, "");
        return convert();
    }

    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        n1.left = n2;
        n1.right = n3;

        Solution solution = new Solution();
        int result = solution.sumNumbers(n1);
        System.out.println("得到的结果：" + result);
    }
}

Python 代码2（推荐）：（使用递归）使用 cumsum 这个概念，即开始遍历到这个根结点的之前，已经有了 cumsum ，代码写出来也是非常简洁。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def sumNumbers(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        res = []
        self.__dfs(root, 0, res)
        return sum(res)

    # Python 中对于基础的数据类型是值传递，即复制
    def __dfs(self, root, cum_sum, res):
        if root is None:
            return None
        if root.left is None and root.right is None:
            # 结算
            res.append(cum_sum * 10 + root.val)
            return
        self.__dfs(root.left, cum_sum * 10 + root.val, res)
        self.__dfs(root.right, cum_sum * 10 + root.val, res)

Java 代码3：

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


import java.util.ArrayList;
import java.util.List;

// 我的思路：这个写法，画个图就非常清晰了，抓住二叉树的特点

public class Solution2 {

    private int sumNumbers(TreeNode node, int cumsum) {
        if (node == null) {
            return 0;
        }
        cumsum = 10 * cumsum + node.val;
        if (node.left == null && node.right == null) {
            return cumsum;
        }
        return sumNumbers(node.left, cumsum) + sumNumbers(node.right, cumsum);
    }


    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return sumNumbers(root, 0);
    }

    public static void main(String[] args) {
        // write your code here
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        n1.left = n2;
        n1.right = n3;

        Solution2 solution2 = new Solution2();
        int result = solution2.sumNumbers(n1);
        System.out.println("得到的结果：" + result);
    }
}

还有一种解法，修改了原二叉树的结点的值。

Python 代码：

# 129. 求根到叶子结点数字之和
# 给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子结点的路径都代表一个数字。
# 例如，从根到叶子结点路径 1->2->3 代表数字 123。
# 计算从根到叶子结点生成的所有数字之和。
# 说明: 叶子结点是指没有子结点的结点。

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:

    def __init__(self):
        self.res = 0

    def sumNumbers(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
        if root.left:
            # 如果左边非空
            root.left.val += root.val * 10
        if root.right:
            # 如果右边非空
            root.right.val += root.val * 10
        # 如果左边右边都为空，就可以结算了
        if root.left is None and root.right is None:
            self.res += root.val
        # 前序遍历
        self.sumNumbers(root.left)
        self.sumNumbers(root.right)
        return self.res

（本节完）

LeetCode 第 129 题：求根到叶子结点数字之和

Python 代码：使用递归，使用 cumsum 这个概念，即开始遍历到这个根结点的之前，已经有了 cumsum ，代码写出来也是非常简洁。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def sumNumbers(self, root):
        res = []
        self.__dfs(root, 0, res)
        return sum(res)

    # Python 中对于基础的数据类型是值传递，即复制
    def __dfs(self, root, cum_sum, res):
        if root is None:
            return None
        if root.left is None and root.right is None:
            # 结算
            res.append(cum_sum * 10 + root.val)
            return
        self.__dfs(root.left, cum_sum * 10 + root.val, res)
        self.__dfs(root.right, cum_sum * 10 + root.val, res)

LeetCode 第 129 题：给定一棵二叉树，每个节点只包含数字 0-9，从根节点到叶子节点的每条路径可以表示成一个数，求这些数的和

Python 代码：

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def sumNumbers(self, root):
        res = []
        self.__dfs(root, 0, res)
        return sum(res)

    # Python 中对于基础的数据类型是值传递，即复制
    def __dfs(self, root, cum_sum, res):
        if root is None:
            return None
        if root.left is None and root.right is None:
            # 结算
            res.append(cum_sum * 10 + root.val)
            return
        self.__dfs(root.left, cum_sum * 10 + root.val, res)
        self.__dfs(root.right, cum_sum * 10 + root.val, res)

文章作者： liweiwei1419
文章链接： https://liweiwei1419.gitee.io/leetcode-algo/2017/12/03/leetcode-algo/0129-sum-root-to-leaf-numbers/
版权声明： 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
递归 二叉树
赏
评论
 上一篇
「力扣」第 199 题：二叉树的右视图 「力扣」第 199 题：二叉树的右视图
「力扣」第 199 题：二叉树的右视图题解地址：DFS 和 BFS（Python 代码）。 说明：文本首发在力扣的题解版块，更新也会在第 1 时间在上面的网站中更新，这篇文章只是上面的文章的一个快照，您可以点击上面的链接看到其他网友对本文的
2017-12-04 专题 12：树
递归 二叉树
下一篇 
「力扣」第 104 题：求一棵二叉树的最大深度（简单） 「力扣」第 104 题：求一棵二叉树的最大深度（简单）
「力扣」第 112 题：Path Sum传送门：112. 路径总和。 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 示例:给定如下二叉树
2017-12-02 专题 12：树
递归 二叉树
  目录