leetcode：129. 求根节点到叶节点数字之和

题目链接

        129. 求根节点到叶节点数字之和 - 力扣（LeetCode）

题目描述

解法1：深搜

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void dfs(TreeNode* root, int vAl,vector<int>& v_sum){if(root->left == nullptr && root->right == nullptr){int v_vAl = vAl * 10 + root->val;v_sum.push_back(vAl * 10 + root->val);return; }if(root->left == nullptr){int v_vAl = vAl * 10 + root->val;dfs(root->right,vAl*10 + root->val,v_sum);return;}if(root->right == nullptr){dfs(root->left,vAl*10 + root->val,v_sum);return;}int v_vAl = vAl * 10 + root->val;dfs(root->left,v_vAl,v_sum);dfs(root->right,v_vAl,v_sum);}int sumNumbers(TreeNode* root) {vector<int> v_sum;dfs(root,0,v_sum);return accumulate(v_sum.begin(),v_sum.end(),0);}
};

深搜与递归的区别

        汉诺塔问题是纯递归，我们将拿汉诺塔问题举例：leetcode:面试题 08.06. 汉诺塔问题-CSDN博客

1. 首先要明白三件事。第一件事：深搜的本质就是递归。第二件事：了解到深搜的本质是递归对于了解深搜来讲，毫无意义，反而有可能造成误导。第三件事：深搜和纯递归大不一样。
2. 对于计算机来讲什么是递归：函数在函数体中调用自身，就会在语法上，不断进入自己的函数体，不断调用自己，直到遇到终止条件，返回。这个过程叫做递归。这个过程是：函数层层调用自身，遇到终止条件，层层返回；层层调用就是“递”，层层返回就是“归”。于是叫做递归。
3. 什么叫纯递归：要解决本问题，先解决子问题，要解决子问题，先解决子问题的子问题，于是层层往下递，遇到最小问题，最小问题可直接解决，最小子问题被解决之后，向上一层归，上一层在下一层问题解决之后，可以直接解决本层问题，再向本层的上一层归。于是解决塔尖层问题。（老贾名言：塔尖）
4. 纯递归如何利用计算机的递归：纯递归利用计算机递归机制，在一层层往下递的过程中，建立递归结构，这个递归结构规定了如何一层层向上归。在一层层往下递的过程中，遇到可直接解决的子问题后，解决这个子问题，然后向上层层归。在一层层归的过程中把问题一步步解决。
5. 纯递归的递：之所以可以递，是因为每个子问题又有相同的处理逻辑，那就是：先解决自己的子问题，再以相同的操作解决自己的问题
6. 纯递归的归：之所以可以归，是因为最小子问题有直接答案或者说可以直接解决，那么本层解决了问题，向上归，上面这一层在自己的下一层已经解决问题的基础上，可以直接按照同一个逻辑解决自身问题。于是问题得以解决。
7. 也就是说纯递归的递为归，指明了路径。
8. 深搜怎么说：深搜借助计算机的递归机制，在不断往下递的过程中，不断得到信息，不断处理信息，来到最后一层时，目标信息构建完毕。也就是说深搜依赖于：递。归的过程对于深搜来讲，没有意义。