树的练习3--------1022从根到叶的二进制数之和

前言

前面做了一道题目，感觉已经摸到递归大道的门把手了，现在做这个题还是有点模糊，知道怎么去做，但是不知道怎么去实现，现在看完题解以后，又对递归多了一点理解。

题目：点这里

解法

/** * 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 { int sum; void sumRoot(TreeNode* root,int pro){ if(root->left==nullptr&&root->right==nullptr){ sum+=pro*2+root->val; }//递归出口 if(root->left!=nullptr){ sumRoot(root->left,pro*2+root->val); } if(root->right!=nullptr){ sumRoot(root->right,pro*2+root->val); } } public: int sumRootToLeaf(TreeNode* root) { sum=0; sumRoot(root,0); return sum; } };

这个题目的思路就是利用前缀值pro和总值sum配合来求咱们的最终结果，具体过程就是将一条路线从头加到尾，然后回到上一层函数，选择不同子节点，再得到另外的结果，所有的结果加在一起就是最终结果。实现逻辑还是很清晰的，首先递归出口就是当当前根节点是叶子节点时，让sum加上pro×2在加上当前节点的值。然后递归内部 呢，就是利用两个if语句，要么往左走，要么往右走，组成所有可能的组合，得到我们想要的数。

反思

如果想从后往前(从里往外)传递值，就需要利用return;

如果想从前往后(从外往里)传递值，就需要将待传的值放在函数的参数列表上。