一 前言
最近看到一个大神说的一些小tips，关于程序员如何迅速找到状态，他提供的一个方法就是每天可以先做一道编程题目，这样可以迅速帮我们找到状态和感觉，个人尝试了几天，感觉效果还不错。主要尝试的是leetCode中的题目，话不多说，有兴趣的同学可以和我一起刷起来~
二 题目
今天我们带来的题目一道关于树的题目：
Given a binary tree containing digits from0-9only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path1->2->3which represents the number123.
Find the total sum of all root-to-leaf numbers.
For example,
1
/ \
2 3
The root-to-leaf path1->2represents the number12.
The root-to-leaf path1->3represents the number13.
Return the sum = 12 + 13 =25.
题目的大致意思就是，给你一棵二叉树，将根节点到叶子节点的数字从高位到低位排列起来形成一个数字，最后将所有路径形成的数字加和，返回这个和值。
三 思路分析及代码
拿到这个题目我们先分析一下他的关键点在于能够得到一条路径形成的和值，对于一个节点来说，假设我们知道它之前路径上的形成的数字为n，那么当访问到该节点时形成的数字就变为10*n + currentNode->val(currentNode是当前节点，val是它对应的值)。按照这个思路我们遍历每一条从根节点到叶子节点的路径，最终进行加和就是我们要的结果。那么说道遍历树我们大致有三种方式：前序（preorder）、中序（inorder）、后序（postorder）。按照上面的思路显然采用前序遍历方式最为合适，也就是说每当访问到当前节点就进行加和累积，然后再去访问他的左右子树。有了这个思路，那么我们的代码就不难了。
代码如下：
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int preorderSumNumbers(int sum, TreeNode *root) {
if (root == NULL) {
return 0;
}
sum = sum * 10 + root->val;
if (root->left == NULL && root->right == NULL) {
return sum;
}
//递归访问该节点的左右子树
return preorderSumNumbers(sum, root->left) + preorderSumNumbers(sum, root->right);
}
int sumNumbers(TreeNode *root) {
if (root == NULL) {
return 0;
}
int sum = 0;
return preorderSumNumbers(sum, root);
}
};
四 后记
上面仅仅是我的思路，大家有更好的想法可以一起交流，期待和大家一起进步~
网友评论