递归如何书写？

目录

第一步：首先你分析问题，要有递归的思路，知道要递归什么来解决问题。

第二步：先按照思路（第一层）写出函数的定义与函数体

第三步：根据函数的定义与函数体进一步确定需要的参数

第四步：最后还要设定最后一层递归的终止条件，以免一直循环下去。

---

例题：给定一棵树的前序遍历数组，判断这棵树是不是二叉搜索树。

第一步：首先你分析问题，要有递归的思路，知道要递归什么来解决问题。

比如上面这个通过前序遍历判断搜索二叉树，首先我们要清楚二叉搜索树的定义。

根据定义，我们不难得出思路，先判断这颗二叉树的左子树（不为空的话）的所有结点是不是小于它的根结点，再判断右子树（不为空的话）的所有结点是不是大于它的根结点。

然后递归判断其左右子树（如果有的话）是不是也满足这个条件。

另外的话你也要清楚前序遍历的特点，第一个结点一定为根节点，然后的话遍历顺序为根结点->左子树->右子树。

结合搜索二叉树，我们可以得出第一个点为根结点，然后往后找，第一个比根结点小的树为左子树的根结点，第一个比根节点大的为右子树的根节点，左子树根节点与右子树根结点之间为左子树的前序遍历序列，右子树之后为右子树的前序遍历序列。

我们只需要看左子树的序列是不是都比根结点的数据小，右子树的序列是不是都比根节点的数据大。然后的话递归遍历左右子树的前序遍历序列看看是不是符合这个特点。

第二步：先按照思路（第一层）写出函数的定义与函数体

一般的话写函数都是先确定函数的定义与输入，然后按照思路写输出。

而递归函数的话我认为要先写思路和定义再写输入。

bool isBST() {
	int rootData=tree[leftBound].data;
	//寻找第一个比根结点小的数是左子树的根结点，
	//寻找第一个比根结点大与或等于的数即时右子树的根节点
	int leftRoot=-1,rightRoot=-1;
	for(int i=1; i<=n-1; i++) {
		if(tree[i].data<rootData&&leftRoot==-1) {
			leftRoot=i;
		} else if(tree[i].data>=rootData&&rightRoot==-1) {
			rightRoot=i;
			break;
		}
	}
    bool haveLeft=(leftRoot!=-1);//是否存在左子树
	bool haveRight=(rightRoot!=-1);//是否存在右子树
    //	根据左子树根结点和右子树根结点即可划分出左右子树
    //	遍历左子树，看看是不是都比根结点小（如果有的话）
	if(haveLeft) {
		for(int i=leftRoot; i<=rightRoot-1; i++) {
			if(rootData<=tree[i].data) {
				return false;
			}
		}
	}
    //遍历右子树，看看是不是都比根结点大（如果有的话）
	if(haveRight) {
		for(int i=rightRoot; i<=0; i++) {
			if(rootData>tree[i].data) {
				return false;
			}
		}
	}

	//子树也要满足是二叉搜索树（如果有的话）
	if(haveLeft&&haveRight) {
        //左子树
		if(!isBST())
			return false;
        //右子树
		if(!isBST())
			return false;
	} else if(haveLeft&&!haveRight) {
		if(!isBST())
			return false;
	} else if(!haveLeft&&haveRight) {
		if(!isBST())
			return false;
	}

	return true;
}

第三步：根据函数的定义与函数体进一步确定需要的参数

上面的话我们的话我们肯定需要有一个tree数组代表数，另外的话我们上面的遍历是遍历整棵树，是从0到n-1，但是为了这个函数能够复用，所以我们需要传入leftBound和rightBound，即数组的左界和有界来确定一颗树。

添加参数并修改代码：

bool isBST(TreeNode tree[],int leftBound,int rightBound) {
	int rootData=tree[leftBound].data;
	//寻找第一个比根结点小的数是左子树的根结点，
	//寻找第一个比根结点大与或等于的数即时右子树的根节点
	int leftRoot=-1,rightRoot=-1;
	for(int i=leftBound+1; i<=rightBound; i++) {
		if(tree[i].data<rootData&&leftRoot==-1) {
			leftRoot=i;
		} else if(tree[i].data>=rootData&&rightRoot==-1) {
			rightRoot=i;
			break;
		}
	}
//	根据左子树根结点和右子树根结点即可划分出左右子树
//	遍历左子树，看看是不是都比根结点小
	bool haveLeft=(leftRoot!=-1);
	bool haveRight=(rightRoot!=-1);
	if(haveLeft) {
		for(int i=leftRoot; i<=rightRoot-1; i++) {
			if(rootData<=tree[i].data) {
				return false;
			}
		}
	}
	if(haveRight) {
		//遍历右子树，看看是不是都比根结点大
		for(int i=rightRoot; i<=rightBound; i++) {
			if(rootData>tree[i].data) {
				return false;
			}
		}
	}

	//子树也要满足是二叉搜索树
	if(haveLeft&&haveRight) {
		if(!isBST(tree,leftRoot,rightRoot-1))
			return false;
		if(!isBST(tree,rightRoot,rightBound))
			return false;
	} else if(haveLeft&&!haveRight) {
		if(!isBST(tree,leftRoot,rightBound))
			return false;
	} else if(!haveLeft&&haveRight) {
		if(!isBST(tree,rightRoot,rightBound))
			return false;
	}

	return true;
}

第四步：最后还要设定最后一层递归的终止条件，以免一直循环下去。

这题的话最终的话循环到最后的树一定就只剩下一个点，一个点的话肯定为搜索二叉树。

添加终止条件完成程序。

bool isBST(TreeNode tree[],int leftBound,int rightBound) {
	if(leftBound==rightBound) {
		return true;
	}
	int rootData=tree[leftBound].data;
	//寻找第一个比根结点小的数是左子树的根结点，
	//寻找第一个比根结点大与或等于的数即时右子树的根节点
	int leftRoot=-1,rightRoot=-1;
	for(int i=leftBound+1; i<=rightBound; i++) {
		if(tree[i].data<rootData&&leftRoot==-1) {
			leftRoot=i;
		} else if(tree[i].data>=rootData&&rightRoot==-1) {
			rightRoot=i;
			break;
		}
	}
//	根据左子树根结点和右子树根结点即可划分出左右子树
//	遍历左子树，看看是不是都比根结点小
	bool haveLeft=(leftRoot!=-1);
	bool haveRight=(rightRoot!=-1);
	if(haveLeft) {
		for(int i=leftRoot; i<=rightRoot-1; i++) {
			if(rootData<=tree[i].data) {
				return false;
			}
		}
	}
	if(haveRight) {
		//遍历右子树，看看是不是都比根结点大
		for(int i=rightRoot; i<=rightBound; i++) {
			if(rootData>tree[i].data) {
				return false;
			}
		}
	}

	//子树也要满足是二叉搜索树
	if(haveLeft&&haveRight) {
		if(!isBST(tree,leftRoot,rightRoot-1))
			return false;
		if(!isBST(tree,rightRoot,rightBound))
			return false;
	} else if(haveLeft&&!haveRight) {
		if(!isBST(tree,leftRoot,rightBound))
			return false;
	} else if(!haveLeft&&haveRight) {
		if(!isBST(tree,rightRoot,rightBound))
			return false;
	}

	return true;
}