LeetCode: Sum Root to Leaf Numbers [129]
LeetCode to root sum Numbers 129
2023-09-14 09:10:10 时间
【题目】
Given a binary tree containing digits from 0-9
only, each root-to-leaf
path could represent a number.
An example is the root-to-leaf path 1->2->3
which represents the number 123
.
Find the total sum of all root-to-leaf numbers.
For example,
1 / \ 2 3
The root-to-leaf path 1->2
represents the number 12
.
The root-to-leaf path 1->3
represents the number 13
.
Return the sum = 12 + 13 = 25
.
【题意】
给定一棵二叉树,节点值仅仅可能是[0-9]区间上的值,每一条从根到叶子的节点都能够看成一个整数。现要求把全部路径表示的整数相加,返回和
【思路】
DFS,找到左右的路径,实数化每条路径上组合数。将全部的路径上得到的整数求和。
这里2有个问题:
1. 假设某条路径太长,组合数已经超出了int的上界怎么办
2. 假设终于的和超出了int的上界怎么办
题目没有进一步的说明,我们默认所给的測试用例都保证不会越界。
【代码】
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void dfs(int&result, int num, TreeNode*node){ //result表示全部路径的组合 //num表示根到node的父节点的组合数 if(node){ num=10*num+node->val; //计算从根到当前节点的组合数 if(node->left==NULL && node->right==NULL){ result+=num; //已经找到一个条路径的组合数,累加到result上 return; } if(node->left) dfs(result, num, node->left); if(node->right) dfs(result, num, node->right); } } int sumNumbers(TreeNode *root){ if(root==NULL)return NULL; int result=0; int num=0; dfs(result, num, root); return result; } };
相关文章
- Leetcode 之Convert Sorted List to Binary Search Tree(55)
- Java实现 LeetCode 827 最大人工岛(DFS+暴力模拟)
- Java实现 LeetCode 787 K 站中转内最便宜的航班(两种DP)
- Java实现 LeetCode 771 宝石与石头(这是真暴力)
- Java实现 LeetCode 438 找到字符串中所有字母异位词
- Java实现 LeetCode 400 第N个数字
- 【LeetCode算法-13】Roman to Integer
- LeetCode(112):路径总和
- LeetCode:114_Flatten Binary Tree to Linked List | 将一棵二叉树变成链表的形式 | Medium
- [LeetCode] Integer to English Words
- [LeetCode] String to Integer (atoi)
- [LeetCode] Fraction to Recurring Decimal
- LeetCode-2379. 得到 K 个黑块的最少涂色次数【字符串,滑动窗口】
- LeetCode 121 Best Time to Buy and Sell Stock
- Leetcode 11. 盛最多水的容器(终于解决)
- Leetcode 2259. 移除指定数字得到的最大结果(可以,一次过)
- leetcode 141. 环形链表 js 实现
- LeetCode 122 Best Time to Buy and Sell Stock II
- Leetcode:best_time_to_buy_and_sell_stock_II题解
- leetcode 405. Convert a Number to Hexadecimal
- leetcode 453. Minimum Moves to Equal Array Elements
- leetcode 538. Convert BST to Greater Tree
- 【LeetCode】394. 字符串解码