递归问题也是做的不好，总去想每一层调用发生了什么，导致越想越乱。
看到一篇博客写的非常好，记录总结。
原文地址：https://lyl0724.github.io/2020/01/25/1/

另一篇：https://mp.weixin.qq.com/s/-V0jBkPoZHYC2jLfSnQ6-g

解递归题的三部曲：
1、找整个递归的终止条件：递归应该在什么时候结束？
2、找返回值：应该给上一级返回什么信息？
3、本级递归应该做什么：在这一级递归中，应该完成什么任务？

需要总结的题目：

Leetcode 101. 对称二叉树

Leetcode 111. 二叉树的最小深度

Leetcode 226. 翻转二叉树：这个题的备注是最骚的。Mac OS下载神器homebrew的大佬作者去面试谷歌，没做出来这道算法题，然后被谷歌面试官怼了：”我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。”

Leetcode 617. 合并二叉树

Leetcode 654. 最大二叉树

Leetcode 83. 删除排序链表中的重复元素

目标：9.17号之前完成。

二叉树的最小深度

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明: 叶子节点是指没有子节点的节点。
思路：
1、终止条件
2、返回值
3、当前操作

 //注意如果根节点的左或右子树为空的话是构不成子树的。而最小深度是要求从根节点到子树的。当左或右子树为空时，不符合要求。
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;  //递归结束
        int left = minDepth(root->left);  //计算左子树的高度
        int right = minDepth(root->right);  //计算右子树的高度
        if (!left || !right) return left + right + 1;  //如果有一个空，则+1
        return min(left, right) + 1;  //否则最小值+1
    }
};

翻转二叉树

1、终止条件 NULL
2、返回值 跟节点
3、操作 交换左右子树

以下为前序遍历

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {//先序优先遍历
        if(root==NULL) return root;
        // 遍历到null节点时，不用翻转，直接返回它本身
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

合并二叉树

合并这类问题需要注意的是，如果有一棵树为空，则返回另一棵树。

不修改树的结构

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2;
        if (t2 == NULL) return t1;
        // 重新定义新的节点，不修改原有两个树的结构
        TreeNode* root = new TreeNode(0);
        root->val = t1->val + t2->val;
        root->left = mergeTrees(t1->left, t2->left);
        root->right = mergeTrees(t1->right, t2->right);
        return root;
    }
};

修改树的结构，思路都是一样的

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2;
        if (t2 == NULL) return t1;
        // 修改了t1的数值和结构
        t1->val += t2->val;
        t1->left = mergeTrees(t1->left, t2->left);
        t1->right = mergeTrees(t1->right, t2->right);
        return t1;
    }
};

删除排序链表中的重复元素

之前也总结了指针法，这回事递归法。
递归套路解决链表问题：
找终止条件：当head指向链表只剩一个元素的时候，自然是不可能重复的，因此return
想想应该返回什么值：应该返回的自然是已经去重的链表的头节点
每一步要做什么：宏观上考虑，此时head.next已经指向一个去重的链表了，而根据第二步，我应该返回一个去重的链表的头节点。因此这一步应该做的是判断当前的head和head.next是否相等，如果相等则说明重了，返回head.next，否则返回head

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head||!head->next)
            return head;
        head ->next = deleteDuplicates(head ->next);
        if(head ->val == head ->next ->val)
            head = head ->next;
        return head;
    }
};