递归思想的应用之求根节点到叶子节点数字和问题

前言

谈到C/C++算法时，递归是一个绕不开的话题，其根本的思想是问题的拆分，即将一个大问题拆分成一个小问题，小问题又可以拆分成一个更小的问题，那么就可以起到简化问题的作用，从而使问题得到解决，下面我将用一道题目进行讲解，因水平有限，若有不当之处，请各位指正！！

一、题目解析

给定一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。 计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。 示例：

输入：root = [1,2,3] 输出：25 解释： 从根到叶子节点路径 1->2 代表数字 12 从根到叶子节点路径 1->3 代表数字 13 因此，数字总和 = 12 + 13 = 25

二、递归算法的使用

废话不多说，我们直奔主题。 1.讲解算法的原理 老师总是在给我们讲，递归要从宏观的角度来思考问题，话是这样说，但是，如果过程太复杂的话，无法叙述清楚，我们也要考虑微观的过程（从根本来说还是宏观），这道题就是个例子，嘿嘿！

也就是说，我们算出这五个数的和就可以了，当我们走到第三层的5时，我们要得到1258这个个数字，我们必须要知道在到达5之前的12，也就是说如果我们要设计函数的话，那么必须有一个参数为在到达该节点之前已经得到的数字，记住是之前的数字，我们叫作presum对于这种情况来说，就是12，那么，接下来 第一步，presum*10+当前节点的数字 第二步，如果该节点没有子节点，那就把新的presum返回上层 第三步，如果存在子节点，那就那就递归得到其左右节点，直到没有为止，然后依次返回上层。 2.代码实现

3.结果