脚本宝典收集整理的这篇文章主要介绍了LeetCode 129. Sum Root to Leaf Numbers,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
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.
大致题意
给出一个二叉树,从根到叶子的路径可以构造一个数。
例如 1->2->3
可以构造为 123
给出一棵树,求该方法在此树上构造的数的和
举个例子,
1
/
2 3
The root-to-leaf path 1->2 表示数字 12.
The root-to-leaf path 1->3 表示数字 13.
题解
题目类型:DFS
分析题目,实际上一个节点构造的树的和为左子树与节点和右子树与节点构造数的和,很常规的dfs题目
题解如下
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int sumNumbers(TreeNode* root) {
return sum(root, 0);
}
int sum(TreeNode * node, int val) {
if (node == nullptr) return 0;
val = val * 10 + node->val;
// 如果左右为空,返回自己
if (node->right == nullptr && node->left == nullptr) return val; // 左右不为空开始构造数
return sum(node->left, val) + sum(node->right, val);
}
};
以上是脚本宝典为你收集整理的LeetCode 129. Sum Root to Leaf Numbers全部内容,希望文章能够帮你解决LeetCode 129. Sum Root to Leaf Numbers所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。