【递归】7. leetcode 404 左叶子之和

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. 递归的出口：当前节点为空。