永兴县网站建设服务商,做电影网站会违法吗,衡水做wap网站,河南省安阳市安阳县1 题目描述
题目链接#xff1a;左叶子之和
2 解答思路
递归分为三步#xff0c;接下来就按照这三步来思考问题
第一步#xff1a;挖掘出相同的子问题 #xff08;关系到具体函数头的设计#xff09;
第二步#xff1a;只关心具体子问题做了什么 #xff08;关系…1 题目描述
题目链接左叶子之和
2 解答思路
递归分为三步接下来就按照这三步来思考问题
第一步挖掘出相同的子问题 关系到具体函数头的设计
第二步只关心具体子问题做了什么 关系到具体函数体怎么写是一个宏观的过程
第三步找到递归的出口防止死递归 关系到如何跳出递归2.1 相同的子问题函数头设计
相同的子问题寻找二叉树的左叶子就是寻找二叉树的左子树的左叶子和右子树的左叶子。
根据相同的子问题思考具体的方法将所有的左叶子放入到一个vector中最后使用循环将值相加到一起。
下面是leetcode给的接口 int sumOfLeftLeaves(TreeNode* root) {}传入一个TreeNode* 类型的参数返回是左叶子的和int类型。
根据之前的分析我们的参数是一个TreeNode*类型还有一个vector int类型。因为值存储在vector中最终计算所以返回值类型为void。最终函数头的设计如下 void sum(TreeNode* root, vectorint res){}2.2 具体的子问题做了什么函数体的实现
具体子问题做了什么 1.首先判断该节点的左孩子是不是叶子节点如果是则加入到vector中。 2.在当前节点的左子树中寻找 3.在当前节点的右子树中寻找
递归的出口当前节点为空。
最终函数体的书写 void sum(TreeNode* root, vectorint res){if (root nullptr)return;//如果当前节点有左孩子 并且 左孩子为叶子节点if ((root-left) ((root-left-left nullptr) (root-left-right nullptr)))res.push_back(root-left-val); //将左孩子的值加入到vector中//递归左子树sum(root-left, res);//递归右子树sum(root-right, res);}3 总结
class Solution {
public:int sumOfLeftLeaves(TreeNode* root) {vectorint res;sum(root, res);int s 0;for (int i 0; i res.size(); i){s res[i];}return s;}//只要叶子节点void sum(TreeNode* root, vectorint res){if (root nullptr)return;//如果当前节点有左孩子 并且 左孩子为叶子节点if ((root-left) ((root-left-left nullptr) (root-left-right nullptr)))res.push_back(root-left-val); //将左孩子的值加入到vector中//递归左子树sum(root-left, res);//递归右子树sum(root-right, res);}
};1. 相同的子问题寻找二叉树的左叶子就是寻找二叉树的左子树的左叶子和右子树的左叶子。
2. 具体子问题做了什么首先判断该节点的左孩子是不是叶子节点如果是则加入到vector中。在当前节点的左子树中寻找。在当前节点的右子树中寻找。
3. 递归的出口当前节点为空。
