1 题目描述
题目链接:左叶子之和
2 解答思路
递归分为三步,接下来就按照这三步来思考问题
第一步:挖掘出相同的子问题 (关系到具体函数头的设计)
第二步:只关心具体子问题做了什么 (关系到具体函数体怎么写,是一个宏观的过程)
第三步:找到递归的出口,防止死递归 (关系到如何跳出递归)
2.1 相同的子问题(函数头设计)
相同的子问题:寻找二叉树的左叶子,就是寻找二叉树的左子树的左叶子和右子树的左叶子。
根据相同的子问题,思考具体的方法:将所有的左叶子放入到一个vector中,最后使用循环将值相加到一起。
下面是leetcode给的接口:
int sumOfLeftLeaves(TreeNode* root) {}
传入一个TreeNode*
类型的参数,返回是左叶子的和,int
类型。
根据之前的分析,我们的参数是一个TreeNode*
类型,还有一个vector< int>
类型。因为值存储在vector
中,最终计算,所以返回值类型为void
。最终函数头的设计如下:
void sum(TreeNode* root, vector<int>& res){}
2.2 具体的子问题做了什么(函数体的实现)
具体子问题做了什么:
1.首先判断该节点的左孩子是不是叶子节点
,如果是,则加入到vector中。
2.在当前节点的左子树中寻找
3.在当前节点的右子树中寻找
递归的出口:当前节点为空。
最终函数体的书写:
void sum(TreeNode* root, vector<int>& 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) {vector<int> res;sum(root, res);int s = 0;for (int i = 0; i < res.size(); ++ i){s += res[i];}return s;}//只要叶子节点void sum(TreeNode* root, vector<int>& 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. 递归的出口:当前节点为空。