二叉树相关问题细谈递归（上）

递归

前言

 递归的思想如其名就是递和归，一步一步展开，最后在合回去，从而解决问题，通过每次递归不断改变一定的数据，将大问题转化成一个一个和大问题相似的小问题来求解，只需要简短的程序，一步一步完成某个工作。

举一个生活中的例子

 校长想要知道疫情返校人数，他可以一个一个寝室挨个查，也可以动用院长辅导员等人帮忙统计

递归就是如此

要学会递归，就要深刻了解递归的思想和方法，最重要的是他的逻辑性。

• 首先你要了解写出这个递归函数到底是用来做什么的，这是递归函数的第一要素，递归函数短小精悍，但一定要明确知道自己的需求。
• 在递归的过程中会有前进段和返回段，满足一定的条件就进行前进，如果不满足则return返回，不能死递归下去，不然就会爆栈，这就是递归的第二要素。
• 在明确需求后，找出函数的等价关系式，这是递归的第三要素，会在后边的学习中进行说明。
  以下两道题帮助理解，精彩还在后边。

求n的阶乘

int factorial(int n)
{
 if(n <= 1)
  return 1;
 else
  return n * factorial(n-1);
}

 给这个函数传入参数，如果小于等于1，就返回1，假使传入的值为5，运行时return结果为nfactorical(4)，这个函数的返回值重新开辟了一个函数，传入值为4，这样一直递归，直至传入结果为1，当一个函数返回时，会回到之前进入函数的位置，然后在n=2的函数中继续return，直至函数结束。
通过不断地传递，当遇到限制条件后开始归，如图所示

 这个函数的作用是求n的阶乘，所以函数f(n)的等价关系式是nf(n-1)，在后边的函数中也都一样，改变的是n的值。

求第n个斐波那契数递归解法

int fib(int n)
{
  if (n <= 2)         
    return 1;
    else
      return fib(n - 1) + fib(n - 2);
}

注意：前两个数的结果为1，后边的数都是前两个相加，函数结束的标志是n<=2，函数的功能是实现找到第n个斐波那契数，要知道第n个斐波那契数，就要知道第n-1个斐波那契数和第n-2个斐波那契数，要知道第n-1个斐波那契数，就要知道第n-2和第n-3个斐波那契数，一直递归下来，可以看到，在求第n个斐波那契数时，第n-2个斐波那契数被求了两次，第n-3个斐波那契数被求了3次，如果n非常大的话，利用递归来查找结果，会多余计算很多次。

我们可以来实验一下

#include <stdio.h>
#include <stdlib.h>
int count = 0;//全局变量
int fib(int n)
{
  if (n == 3)
    count++;
  if (n <= 2)
    return 1;
  else
    return fib(n - 1) + fib(n - 2);
}
int main()
{
  fib(10);
  printf("%d", count);
  return 0;
}

运行后如图

 传入10时，仅仅是3的斐波那契数就进行了21次，如果传入的值再大一点呢？

 这个时候使用递归的弊端就显示出来了，虽然代码原理浅显易懂，但有些情况下要进行的运算太多了。

传入50跑了许久都跑不出来。如果数据再大一点的话，会一直开辟栈空间，知道栈空间被耗尽，造成栈溢出。

这道题告诉我们虽然递归逻辑清晰，代码块小，但某种情况下我们还是利用非递归的方式来写。

思路：第三个数是1+1，第四个数是2+1，只要保存更新两个相加数即可。

int fib(int n)
{
  int ret=1,pre=1;//结果
  int older_ret;//第一个加数
  while (n > 2)
  {
    n -= 1;
    older_ret = pre;
    pre = ret;//上一次的结果赋值
    ret = pre + older_ret;
  }
  return ret;
}

总结：

1. 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。

2. 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。

3. 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。

 但是当我们在计算二叉树相关的问题时，在遍历树的过程中递归就非常的好用。

我写了另一篇二叉树及Topk问题,详解了二叉树，感兴趣的朋友可以去看一看。

从基本讲起，随后会有几道力扣题巩固理解

前中后序遍历

二叉树有三种遍历方式

1，前序遍历 根，左，右。

2，中序遍历 左，根，右。

3，后序遍历 左，右，根。

结构体声明如下

typedef int BTDataType;
typedef struct BinaryTreeNode
{
  BTDataType data;
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
}BTNode;

其中根为子树的根节点，左为左孩子节点，右为右节点。

前序遍历

//前序遍历
void BinaryTreePrevOrder(BTNode* root)
{
  if (root == NULL)
  {
    return;
  }
  printf("%d ", root->data);//先访问该节点
  BinaryTreePrevOrder(root->left);//再访问左子树和右子树
  BinaryTreePrevOrder(root->right);
}

 前序遍历就是先访问根节点，然后走左节点，再走右节点，首先访问该节点，然后找他的左，判断条件为如果该节点为空，就停止递，开始归。

假设我们已经有了一个二叉树

递归展开如下：

中序遍历和前序遍历相差不大

//中序遍历
void BinaryTreeInOrder(BTNode* root)
{
  if (root == NULL)
  {
    return;
  }
  BinaryTreePrevOrder(root->left);//先访问左子树
  printf("%d ", root->data);//再访问该节点
  BinaryTreePrevOrder(root->right);//最后访问右子树
}

下边的问题都将利用这个二叉树来进行解释，这个树可以展现出我们会遇到的大多种情况。

递归展开图如下

 上边标注了步骤及打印顺序，遇到有关递归的题目，有不懂的地方只要画一画递归展开图就会豁然开朗

 同样，后序还是更改一下顺序，按照左右根的顺序来访问打印，如果想要更加清晰地建看出，可以访问空节点返回前打印一个*号。

后序代码如下

//后序遍历
void BinaryTreePostOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("*");
    return;
  }
  BinaryTreePrevOrder(root->left);//先访问左子树和右子树
  BinaryTreePrevOrder(root->right);
  printf("%d ", root->data);//最后访问该节点
}

二叉树全局遍历问题

树的节点个数

要找树的节点个数，分析，访问全树，如果为空树就返回，如果不是空树就加1。可以找一个变量来存储这个值，但由于局部变量在一个函数是单个个体，全局变量的安全性不高，我们可以传过来一个指针变量，每当访问到非空节点就解引用加一，空节点就return。

也可以利用返回值直接返回每个函数返回的值。

代码如下

//树的节点个数
int BinaryTreeSize(BTNode* root)
{
  if (root == NULL)
  {
    return;
  }
  return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
  //return root==NULL?0:BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;//三目操作符,前序
}

控制每个函数返回一个值，最后总和起来的就是节点的个数。归的条件是节点为空，返回的是统计的节点个数。

仍然利用上图讲解

递归展开图如下

到了这里，你是否已经开始熟悉递归的思路了。

相同类型的题目，不过要判断条件

叶子节点的个数