[LeetCode] Sum Root to Leaf Numbers
LeetCode to root sum Numbers
2023-09-11 14:17:25 时间
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
.
Tree Depth-first Search
思路:典型dfs 深度搜索
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { private: int m_sum; vector<int> m_vec; int intVec2Int(vector<int> nums) { int num = 0; for(int i = 0; i < nums.size(); i++) { num = num * 10 + nums[i]; } return num; } void dfs(TreeNode* root) { if(root == NULL) return; m_vec.push_back(root->val); if(root->left == NULL && root->right == NULL) { m_sum += intVec2Int(m_vec); m_vec.pop_back(); return; } if(root->left) dfs(root->left); if(root->right) dfs(root->right); m_vec.pop_back(); } public: int sumNumbers(TreeNode *root) { m_vec.clear(); m_sum = 0; dfs(root); return m_sum; } };
相关文章
- Leetcode: Subsets II
- 【LeetCode-面试算法经典-Java实现】【129-Sum Root to Leaf Numbers(全部根到叶子结点组组成的数字相加)】
- JS Leetcode 154. 寻找旋转排序数组中的最小值 II 题解分析
- [LeetCode]Reverse Integer
- mysql更新字段值提示You are using safe update mode and you tried to update a table without a WHERE that uses a KEY column To disable safe mode
- LeetCode之团灭字典序相关题目
- 177、【动态规划】leetcode ——11035. 不相交的线(C++版本)
- 91、【树与二叉树】leetcode ——559.n叉树的最大深度(递归DFS+迭代BFS)(C++版本)
- 【LeetCode】241. Different Ways to Add Parentheses
- 【LeetCode】122. Best Time to Buy and Sell Stock II
- [LeetCode] 1330. Reverse Subarray To Maximize Array Value 翻转子数组得到最大的数组值
- [LeetCode] 1282. Group the People Given the Group Size They Belong To 用户分组
- [LeetCode] 1103. Distribute Candies to People 给人们发糖果
- [LeetCode] 999. Available Captures for Rook 国际象棋中车的可捕获量
- [LeetCode] Most Profit Assigning Work 安排最大利润的工作
- [LeetCode] Max Chunks To Make Sorted 可排序的最大块数
- [LeetCode] Bold Words in String 字符串中的加粗单词
- [LeetCode] Minimum Moves to Equal Array Elements II 最少移动次数使数组元素相等之二
- [LeetCode] Minimum Number of Arrows to Burst Balloons 最少数量的箭引爆气球
- [LeetCode] Best Time to Buy and Sell Stock IV 买卖股票的最佳时间之四
- [LeetCode] Best Time to Buy and Sell Stock III 买股票的最佳时间之三
- [LeetCode] 129. Sum Root to Leaf Numbers 求根到叶节点数字之和
- 《To prune, or not to prune:exploring the efficacy of pruning for model compression》论文笔记
- leetcode 647. Palindromic Substrings回文子串(中等)
- leetcode 167. Two Sum II - Input Array Is Sorted 两数之和 II - 输入有序数组