(Java）leetcode-129 Sum Root to Leaf Numbers（求根到叶子节点数字之和）

心已赠人 2023-02-20 10:40 5阅读 0赞

# 题目描述 #

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

# 思路 #

普通先序遍历即可，每到一个节点更新一次当前数字（旧值\*10+新值），这个数字作为参数传入下一层递归中，由于不是引用变量，所以返回上层时不需要进行回退。每当到达叶子节点时，当前数字加到结果中。

## 代码 ##

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

执行用时：  
0 ms, 在所有 Java 提交中击败了100.00%的用户  
内存消耗：37.5 MB, 在所有 Java 提交中击败了5.55%的用户

发表评论取消回复

表情：

评论列表（有 0 条评论，5人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode129. 求根到叶子节点数字之和

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。例如，从根到叶子节点路径 1->2->3 代表数字 123。计算从根到叶

ゞ浴缸里的玫瑰/ 2023年07月06日 06:11/ 0 赞/ 4 阅读

相关 (Java）leetcode-129 Sum Root to Leaf Numbers（求根到叶子节点数字之和）

题目描述给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。例如，从根到叶子节点路径 1->2->3 代表数字 123。

心已赠人/ 2023年02月20日 10:40/ 0 赞/ 6 阅读

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

题目来源 [129. 求根到叶子节点数字之和][129.] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdG

た入场券/ 2022年12月23日 07:10/ 0 赞/ 199 阅读

相关 129. 求根到叶子节点数字之和（树）

1.题目描述给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。例如，从根到叶子节点路径 1->2->3 代表数字 12

一时失言乱红尘/ 2022年11月21日 04:10/ 0 赞/ 167 阅读

相关 Sum Root to Leaf Numbers（C++求根节点到叶节点数字之和）

（1）递归 / Definition for a binary tree node. struct TreeNode {

深碍√TFBOYSˉ_/ 2022年10月18日 12:57/ 0 赞/ 148 阅读

相关 129. Sum Root to Leaf Numbers

这是一道关于二叉树树的题目，题目的本质是进行遍历各节点。代码如下： class Solution(object): def Get_Sum(sel

Love The Way You Lie/ 2022年05月31日 01:39/ 0 赞/ 178 阅读

相关 LeetCode129. 求根到叶子节点数字之和

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

阳光穿透心脏的1/2处/ 2022年05月11日 09:30/ 0 赞/ 174 阅读

相关 LeetCode 129.Sum Root to Leaf Numbers (求根到叶子节点数字之和)

题目描述：给定一个二叉树，它的每个结点都存放一个 `0-9` 的数字，每条从根到叶子节点的路径都代表一个数字。例如，从根到叶子节点路径 `1->2->3` 代表数字 `

Love The Way You Lie/ 2022年05月08日 06:04/ 0 赞/ 183 阅读

相关 129. Sum Root to Leaf Numbers

Given a binary tree containing digits from `0-9` only, each root-to-leaf path could repr

秒速五厘米/ 2022年05月04日 04:30/ 0 赞/ 153 阅读

相关 leetcode：129. 求根到叶子节点数字之和

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。例如，从根到叶子节点路径 1->2->3 代表数字 123。计算从根到叶

爱被打了一巴掌/ 2021年09月28日 12:50/ 0 赞/ 279 阅读