一、二叉树

一定要描述清楚递归的终止条件和递归过程

1、给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL)
            return 0;
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        return max(left,right)+1;//max()函数，是已经定义好的函数
    }
};

2、翻转二叉树

----------swap()函数，已经定义好的交换函数，可以直接使用-----------------

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == NULL)
            return NULL;
        invertTree(root->left);
        invertTree(root->right);
        swap(root->left,root->right);
        return root;
    }
};

二、二叉树递归的终止条件

不要想当然的给出递归的终止条件，一定要经过分析和验证最后确定递归的终止条件。

1.给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root==NULL)
            return false;
        if(root->left == NULL && root->right == NULL)
            return root->val == sum;
        if(hasPathSum(root->left,sum-root->val))
            return true;
        if(hasPathSum(root->right,sum-root->val))
            return true;
        
        return false;
    }
};

2、给出一个完全二叉树，求出该树的节点个数。

说明：

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例:

输入:
1
/ \
2 3
/ \ /
4 5 6

输出: 6

解法一：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root == NULL)
            return 0;
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

解法二：如果右子树的高度等于整棵二叉树的高度-1的话，那么左子树一定是一棵满二叉树，这个时候我们就很容易的计算出总结点数nodes=2**(h)-1 + 1 +右子树节点数（这里的+1表示root节点）。如果右子树的高度不等于整棵二叉树的高度-1的话，那么左子树不一定是一棵满二叉树，但是有一点可以确定，右子树一定是一棵满二叉树，这个时候我们就很容易的计算出总结点数nodes=2**(h-1)-1 + 1 +左子树节点数（这里的+1表示root节点）

3、给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

1
/ \
2 2
\ \
3 3

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL)
            return true;
        return leftAndRight(root->left,root->right);
        
    }
    bool leftAndRight(TreeNode* l,TreeNode* r){
        if(l == NULL && r == NULL)
            return true;
        if (l == NULL|| r == NULL)
            return false;
        if(l->val != r->val)
            return false;
        return leftAndRight(l->left,r->right) & leftAndRight(l->right,r->left);
    }
};

4、给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7
返回它的最小深度 2.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root==NULL) return 0;
        TreeNode* node;
        queue<TreeNode*> que;
        int depth=1;
        que.push(root);
        while(!que.empty()){
            int num=que.size();
            while(num-->0){
                node=que.front();
                que.pop();
                if(node->left==NULL&&node->right==NULL) return depth;
                if(node->left!=NULL) que.push(node->left);
                if(node->right!=NULL) que.push(node->right); 
            }
            depth++;
        }
        return depth;

    }
};

三、递归

1、写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：
输入：n = 2
输出：1
示例 2：
输入：n = 5
输出：5

提示：
0 <= n <= 100

菲波那切数列不一定非要用递归来做，因为如果数比较多的时候，用递归会导致一些数重复计算

class Solution {
public:
    int fib(int n) {
        if(n == 0 || n == 1)
            return n;
        int a = 1;
        int b = 0;
        for (int i = 1;i < n;i++){
            a = a+b;
            b = a-b;
            a = a%1000000007;
        }
            return a;
    }
};

2、给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
例如，从根到叶子节点路径 1->2->3 代表数字 123。
计算从根到叶子节点生成的所有数字之和。
说明: 叶子节点是指没有子节点的节点。
示例 1:
输入: [1,2,3]
1
/ \
2 3
输出: 25
解释:
从根到叶子节点路径 1->2 代表数字 12.
从根到叶子节点路径 1->3 代表数字 13.
因此，数字总和 = 12 + 13 = 25.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root) {

        int num1 = 0;
        int num2 = 0;
        sum(root,num1,num2);
        return num2;
            
    }

    //num1指的是将每个节点的值乘以相应的10的倍数，num2是最终加和的结果
    void sum(TreeNode* node,int num1,int& num2){
        if(node == NULL)
            return;
        num1 = num1*10 + node->val;
        if(node->left==NULL && node->right==NULL){
            num2 += num1;
            return;
        }
        sum(node->left,num1,num2);
        sum(node->right,num1,num2);
    }
};

二叉树和递归