数据结构:二叉树的链式结构

一.前言

对二叉树不是很熟悉的可以看看这篇文章:二叉树基础。

我们先看看二叉树结构的图片：

可以发现二叉树表达起来起始非常简单，定义一个有三个成员的结构体，一个成员存数据，另外两个存当前节点的左孩子和右孩子的地址。

但是接下来要学习的不是二叉树的增删查改，你们可能在学习顺序表，链表那些数据结构的时候可能先了解一下它们然后直接上手写这些数据结构的增删查改的函数接口。但是二叉树不一样，二叉树的这种结构本身就不适合这样写，而且增删查改对它也没有意义，如果你需要，完全可以用顺序表，链表它们，而不是用二叉树这种麻烦的结构。链式二叉树的这种结构虽然此时可能没什么用，但学习它可以为后面在学搜索二叉树，红黑树这些打下坚实的基础。

二.二叉树遍历

2.1前序遍历/先根遍历

前序遍历是，先找到根节点，然后找根节点的左子树，找到左子树之后再找右子树。

首先先将这棵树整体看作三个部分：根，左子树，右子树

前序遍历是先遍历根所以此时把1找出来。紧接着我们遍历左子树，此时我们要把左子树当成一棵独立的数，也就是跟刚才遍历的思想一样把此时的数也看成三个部分：

虽然此时2没有右子树，我们仍然当这个空树当成一个整体。此时先遍历根也就是2这个节点，在遍历2的左子树，右子树。现在先遍历2的左子树：

同理把2的左子树当成一个树，先遍历根也就是3这个节点，在遍历3的左子树，右子树。发现3的左子树，右子树都为空说明3的左子树，右子树都遍历完了。现在3这个节点的根，左子树，右子树都遍历完了，也就是说明2的左子树遍历完了，此时我们要开始遍历2的右子树，但是2的右子树是个空树，所以直接返回，也就是说2这颗树的根，左子树，右子树都遍历完了，也可以认为1这个根的左子树全部遍历完了。
自此我们遍历1这棵树的顺序就是：
1，2，3，NULL,NULL，NULL。
这里NULL的意思是说，我们此时访问到的是个空树。

1的左子树遍历完了，接下来我们要遍历1的右数，一样的将这棵树划分成根，左子树，右子树：

因为是前序遍历，所以先找到的是4这个根，紧接着访问4的左树：

同理先访问根节点5，在访问5的左子树，右子树。但是左子树，右子树都为空，直接算访问结束，所以5这颗树就全部访问完成了，也就是说4这棵树的左子树访问结束了，现在开始访问4的右子树。同样：

现在先访问根节点6在访问6的左子树，右子树，因为两个都是空所以直接返回，现在4的左子树，右子树都访问完成了，也就是说最终1的右子树访问结束了。现在整棵树的根节点，左子树，右子树就全部访问结束了。

这个前序遍历看上去十分复杂，其实就是用了一种分治的思想，我们不是一下子就访问整棵树，而是将问题一步一步划分成子问题。然后得出结果。

接下来我们用代码来实现：

//浅浅的建一个二叉树，这个树的样子就是刚才画的那张图

typedef int BTDataType;

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

void test2()
{
	//简单建立一个二叉树
	BTNode n1;
	BTNode n2;
	BTNode n3;
	BTNode n4;
	BTNode n5;
	BTNode n6;

	n1.data = 1;
	n2.data = 2;
	n3.data = 3;
	n4.data = 4;
	n5.data = 5;
	n6.data = 6;

	n1.left = &n2;
	n1.right = &n4;

	n2.left = &n3;
	n2.right = NULL;

	n3.left = n3.right = NULL;

	n4.left = &n5;
	n4.right = &n6;

	n5.left = n5.right = NULL;
	n6.left = n6.right = NULL;
}

现在开始尝试着写一下前序遍历的代码，因为访问的顺序是根左子树，右子树。我们把访问到根节点的时候把这个根节点里面的数据打印出来：

//前序遍历
void PrevOrder(BTNode* root)
{
	//访问根节点
	printf("%d ", root->data);
}

随后我们要访问此时根节点的左子树，方法很简单，用递归的思想，把此时跟的左孩子当成一新的棵的节点来看：

//前序遍历
void PrevOrder(BTNode* root)
{
	printf("%d ", root->data);
	PrevOrder(root->left);
}

这样就把左子树访问完了，紧接着访问这棵树的右子树：

//前序遍历
void PrevOrder(BTNode* root)
{
	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

这样就很好的把这颗树的节点都访问完了，但是还没有完。我们现在考虑一下，这个函数一直走一直走，走到空的时候怎么办？也很容易，此时是个空树的话就直接返回就行，说明这棵树已经访问完了，所以我们在给函数加一个结束条件：

//前序遍历
//前序遍历
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%d ", root->data);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

注意一定要加在函数的的开头，这样每次在递归的时候先判断一下是否为空，是的话就返回，否则继续向下走。

看一下打印出来的结果：

这和上面分析的一模一样。有些人可能会疑惑，几行代码就解决了吗？当然，这就是递归的妙用，将一个大的问题转化成很多相似问题的小问题。如果你觉得不可思议的话，我再来话一个递归的流程图，来帮助理解：

刚开始是1这个节点因为它不是空，走到printf函数这里，然后继续往下走，此时开始递归调用走1的左子树，先打印2这个节点然后继续找2的左子树：

然后继续往下走先打印3这个节点，然后继续向下走：

但是3的左子树是空，所以直接返回顺便打印一下NULL。紧接着开始走3的右子树：

但是右子树同样是空，打印一个NULL然后返回。这样3这个节点所在的函数就走完了。

做到这里也就是说2的左子树全部走完了，换句话说2所在的这个函数的PrevOrder(root->left);这个函数完成了，继续往后走，最终1这个节点在遍历左子树是的步骤就是下面这些：

这样1的左子树就全部完成了。右子树我在这里就不去画了。

2.2中序遍历/中根遍历

中序遍历：先遍历左树，在遍历根，最后在遍历右数。

顺序虽然和前序遍历不同，但是思想大致一样：

这里仍然把整体当作一棵完整的数，但是我们先不打印1这个节点，直接去遍历1的左子树：

同样先不打印2这个节点，先找2的左子树：

到这里仍然是一样的先不看3这个节点，先看3的左子树，但是左子树是空所以打印一个NULL就返回，现在再找3这个根节点，最后再找3的右子树，因为也是空所以打印一个NULL返回。这样打印的顺序就是NULL,3,NULL。现在3这棵树就找完了，随后回过头找2这个节点把2也打印出来，再找2的右子树，因为这棵树是个空所以打印个NULL就直接返回。这样1的左子树就全部找完了，此时在打印1这个节点，继续找1的右子树…

右子树的过程也一样，这里就不再赘述，现在直接看代码实现：

//中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

变化也很简单，既然是中序遍历，就先找此时节点的左子树就行，找完了在打印节点，然后再找右子树。

在看打印结果：

2.3后序遍历/后根遍历

后序遍历是：先遍历左子树，在遍历右子树，最后遍历这个根节点

经过上面两个遍历的学习，后序遍历应该不会这么难理解。

遇到1这个节点的时候先不管它，直接去找它的左子树，找一圈找完之后返回来，仍然不管它，继续找右子树，全部找完之后在打印根节点。

直接看代码：

//后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

再来看结果：

2.4层序遍历

层序遍历和刚才那三种情况不一样，它是一层一层遍历，像这棵树：

实际打印出的结果是1，2，4，3，5，6

层序需要用到队列来辅助完成遍历，具体步骤大约是：

开始先将1这个节点插入到队列中，然后将此时的数据打印出来。然后再把1取出来，顺便把1的两个孩子:左孩子，右孩子插入进去，注意这里队列里存放的是一个节点，而不是这个节点里的数据，因为只是存数据的话，就找不到这个节点的两个孩子了：

然后再把结点2取出来顺便打印这个节点的数据，再把2的两个孩子插入进去，如果孩子为空就不插入：

继续把4这个节点取出来打印，并且将4的两个孩子插入进去：

因为为空就不插入了，所以最后将3，5，6一个一个取出来，当列表为空的时候结束。

这是层序遍历的大致思路。现在用代码来实现，但是我目前还没学C++，只能把C语言自己写的关于队列的函数拿过来用

//二叉树节点的定义
typedef char BTDataType;

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

//队列结构的定义
typedef BTNode* QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

//删除
void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	
	return pq->size == 0;
}

//入对列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("QueuePush");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}

//出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}

//取出队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

//取出队列头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}

//队列大小
int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

层序遍历：

//层序遍历
void LevelOrder(BTNode* root)
{
	//定义一个队列并初始化
	Queue pq;
	QueueInit(&pq);

	//入队列，将根节点放到队列中
	QueuePush(&pq, root);

	while(!QueueEmpty(&pq))
	{
		//出队列，然后将这个节点的两个孩子传进去
		QDataType tmp = QueueFront(&pq);
		QueuePop(&pq);
		//出队列后顺便把这个节点的值打印出来
		printf("%c ", tmp->data);

		//如果某个孩子为空就不放到队列里了
		if (tmp->left)
		{
			QueuePush(&pq, tmp->left);
		}
		if (tmp->right)
		{
			QueuePush(&pq, tmp->right);
		}
	}

	QueueDestroy(&pq);
}

最后看看结果：

顺序确实是一行一行打印的。

这样确实可以打印出来，现在加个条件，一行一行的打印，像这样：

这怎么做呢？其实很简单，定义一个新的变量size即可，size代表当前层数的节点个数。

当1这个节点进到队列之后，可以认为此时的size为1，所以可以在代码里添加这几行代码：

然后1出去，把1的左右孩子节点进到队列中，但是我们现在希望只把1这个节点出出去，之前写的代码，没有这个概念，代码在出1这个节点后立马就把后面的2节点删除出去了，所以现在我们把出队列的代码在放到一个循环中：

这时候1这个节点出去并打印之后，就跳出循环，并且换个行，此时我们更新一下size的值，因为当前节点只是第二层的，size自然而然就设置成了第二层的节点个数。

在回到循环也是一样因为size为2,里面嵌套的循环只会循环两次，只是把第二层节点弹出并打印…这样就可以做到把树的节点一层一层的打印

//层序遍历
void LevelOrder(BTNode* root)
{
	Queue pq;
	QueueInit(&pq);

	int size = 0;
	//入队列
	QueuePush(&pq, root);
	size = 1;

	while(!QueueEmpty(&pq))
	{
		while(size--)
		{
			//出队列，然后将这个节点的两个孩子传进去
			QDataType tmp = QueueFront(&pq);
			QueuePop(&pq);
			printf("%d ", tmp->data);
			if (tmp->left)
			{
				QueuePush(&pq, tmp->left);
			}
			if (tmp->right)
			{
				QueuePush(&pq, tmp->right);
			}
		}

		printf("\n");
		size = QueueSize(&pq);
	}

	QueueDestroy(&pq);
}

2.5二叉树的销毁

因为一般情况二叉树创建的节点都是用malloc创建的，在用完应该记得用free销毁，销毁的过程也要用到递归。同样将销毁分成简单的子问题，这里一定要注意一个顺序，要先销毁当前节点的左右子树，最后在销毁当前节点，如果反过来，先把节点销毁完了，你就找不到它的左右子树的位置了：

//二叉树销毁
void TreeDestory(BTNode* root)
{
	TreeDestory(root->left);
	TreeDestory(root->right);
	free(root);
}

最后在考虑终止条件：

//二叉树销毁
void TreeDestory(BTNode* root)
{
	if (root == NULL)
		return;

	TreeDestory(root->left);
	TreeDestory(root->right);
	free(root);
}

如果是空就代表是空树，不用销毁，直接返回就行。其实这里可以传一个二级指针过来的，因为你虽然把root这个根节点销毁了，但是你没有把这个root置空，但不写也不要紧，这个函数调用完自己想起来把它置空也行。

三.二叉树节点个数

现在有一棵树，希望通过遍历能求出这棵树的节点个数：

这里我们同样用递归来写，将一个复杂的问题，分解成一个一个简单的子问题。这棵树的所有节点我们可以看成：根节点的个数+左子树节点个数+右子树节点个数。

//二叉树节点个数
int TreeSize(BTNode* root)
{
	return TreeSize(root->left) + TreeSize(root->right) + 1;
}

因为根节点不可能有很多，只有1个，所以结果就是左子树的个数和右子树个数之和在加1.

现在子问题的思路已经写出来了，现在还需要一个停止条件，不能让递归这样无限递归下去，也就是大思路已经写出来了，假设我们一直递归下去现在走到了3这个节点，然后我们再来计算3的左子树和右子树：

我们发现3的左右子树都是NULL，所以现在我们需要多加一个树是空的条件，这样就能保证我们的程序正常运行：

//二叉树节点个数
int TreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	return TreeSize(root->left) + TreeSize(root->right) + 1;
}

因为空树不算节点，所以直接返回0.

四.二叉树叶子节点的个数

这个比刚才求总节点的稍微难一点，但技巧找到了也不是什么难事：

同样用递归，用分治的思想，整棵树的叶子节点个数就相当于左子树叶子节点个数加右子树叶子节点个数。所以我们把两个子树的叶子节点个数加起来直接返回即可：

//二叉树叶子节点个数
int TreeLeafSize(BTNode* root)
{
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

但是我们得再次之前先判断一下是不是叶子节点，是的话就返回1，否则就不返回。如果不加这些东西的话，直接返回就返回了一个寂寞，肯定是行不通的：

//二叉树叶子节点个数
int TreeLeafSize(BTNode* root)
{
	if (root->left == NULL && root->right == NULL)
		return 1;

	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

这里判断，如果当前节点的两个孩子都是空，就说明它是叶子节点。

现在每个子问题就基本写完了，我们同样考虑一下如果函数一直递归下去会怎么样：
但是我们发现每次函数走到叶子节点的时候就直接返回1了，根本走不到return TreeLeafSize(root->left) + TreeLeafSize(root->right);这一步，但是这样就能说成功了吗？当然还需要考虑一些其它情况像下面的2这个节点：

它的右子树是空的，但是没达到叶子节点的要求，函数下一次递归时root就会变成空指针，此时在函数里对空指针解引用就会发生错误，所以我们还要加一个限制条件：

//二叉树叶子节点个数
int TreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;

	if (root->left == NULL && root->right == NULL)
		return 1;

	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

五.二叉树的高度

求高度的难度又要高一些，我们现在要做的就是如何将这题转换成子问题。

这棵树的高度就相当于，左子树的高度和右子树的高度中最高的那棵子树的高度加1：

所以我们可以这样写：

//二叉树高度
int TreeHight(BTNode* root)
{
	int left = TreeHight(root->left);
	int right = TreeHight(root->right);

	return left > right ? left + 1 : right + 1;
}

先将左右两棵树的结果保存下来，然后在判断把最高的那棵树的值留下来+1在返回。

现在在考虑结束条件，如果我们一直递归，一直到最后的叶子节点时：

发现如果此时的root是空的话，直接返回0就行。这样3这棵树左子树高度是0，右子树高度是0，所以返回0+1也就是1，这样就把3这棵树的高度返回了。

//二叉树高度
int TreeHight(BTNode* root)
{
	if (root == NULL)
		return 0;

	int left = TreeHight(root->left);
	int right = TreeHight(root->right);

	return left > right ? left + 1 : right + 1;
}

六.二叉树第K层的节点个数

到这里难度又提高了不少，同样将这个问题分解：

现在我们求这棵树第四层的节点个数，是不是可以看成左子树第3层节点个数+右子树第3层节点个数，然后继续划分…

直到这些我们就可以这样写：

//二叉树第K层节点
int TreeLevelKSize(BTNode* root, int k)
{
	return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}

然后像这样一直递归，一直递归直到K为1的时候是不是就找到了我们希望找到的那一层？所以我们在此基础上加一个限制条件：

//二叉树第K层节点
int TreeLevelKSize(BTNode* root, int k)
{
	if (k == 1)
		return 1;

	return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}

但是这就完了吗？当然不是，如果此时root是空，并且K还没到1的时候，下面对NULL解引用就会出错，而且此时K==1时刚好这个树是空，就说明此时不应该返回而是0，所以我们最后还要加一个限制条件：

//二叉树第K层节点
int TreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;

	if (k == 1)
		return 1;

	return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}

七.找二叉树的节点

这个也比较复杂，意思就是找下面这个二叉树的一个指定的节点，并且把这个节点的地址返回出来，这个我们假如要找7这个节点：

经过前面几道题的磨练，思路应该能想出来一个大概：递归遍历嘛，如果一直递归最后是空的时候就返回空，然后用if判断，如果找到了就返回此时节点的地址，如果没找到就递归找左树，右树：

//查找x的节点
BTNode* TreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	TreeFind(root->left, x);
	TreeFind(root->right, x);
}

但是这样写只写对了一半，现在我来画一下递归展开图来看看哪些地方需要改进：

首先递归一直到3这个节点的位置，因为是叶子节点，左右两个孩子都为空，然后返回空，一直到这里都很正常，但是这两个函数都走完了然后返回什么呢？(就是上面黑色线的那个地方)。这里第一个问题就找到了，我们要在这个地方加一个返回值，说明目前走的这条路径没有找到需要的值：

//查找x的节点
BTNode* TreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* ret1 = TreeFind(root->left, x);
	BTNode* ret2 = TreeFind(root->right, x);
	return NULL;
}

然后我们继续画图：

这里发现虽然找到了需要找的地址，也确实成功返回了，但是返回后的地址没有用任何东西接收，也就是说你确实找到了，但是找完之和立马又丢掉了。因为这种原因，现在还要在改一下代码：

//查找x的节点
BTNode* TreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;

	BTNode* ret1 = TreeFind(root->left, x);
	if (ret1)
		return ret1;

	BTNode* ret2 = TreeFind(root->right, x);
	if (ret2)
		return ret2;

	return NULL;
}

这里我们拿ret1,ret2分别接收左右两个子树里找到的地址，但这里不是两个地址都接收完在返回，而是先找左边，如果左边找到了就不用找右边了。如果左右两棵子树都没找到就返回NULL。

八.题目

8.1判断单值二叉树

原题传送门：力扣
题目：

题目的大概意思是给你一个二叉树，如果这个二叉树的节点的值都相同则返回true，只要有一个不相同就返回false.

这个题目可以将问题拆分成一个一个的小问题：
先判断根节点的值和它的左右两个子节点的值是否相等，如果都相等就说明目前是没有问题的，然后继续递归用同样的办法找左子树和右子树。

bool isUnivalTree(struct TreeNode* root){
    if(root->val != root->left->val)
        return false;
    if(root->val != root->right->val)
        return false;
}

这里我们如果发现有一个判断不相等就返回false,记住这里判断的是不相等，而不是相等，因为只要直到有一个是不相等，它的最终结果肯定是false,但是现在三个值相等不代表下面的值也相等。判断相等不能拿到结果，所以这里判断不相等。

如果两个if判断完之后发现都相等，此时就应该开始写递归循环了，判断当前节点的左子树和右子树：

bool isUnivalTree(struct TreeNode* root){
    if(root->val != root->left->val)
        return false;
    if(root->val != root->right->val)
        return false;

    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

一直递归下去，因为返回的是bool值，所以这里不需要定义变量来接收返回值，因为当前节点的左右两个子树返回的值都为真，最终结果才是真，所以这里用的是&&符号。

大致思路已经写好了，现在在考虑一下一直递归到最后会怎样，也就是此时的节点是NULL的情况：

bool isUnivalTree(struct TreeNode* root){
    if(root == NULL)
        return true;

    if(root->val != root->left->val)
        return false;
    if(root->val != root->right->val)
        return false;

    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

如果是空的话直接返回true就行，总不能因为你是空树，我就当你这个值和root不相等吧，这样的话就不管什么树都不是单值二叉树了，因为不管什么树都会有空树。

但是写到这里还没有结束，因为这个代码还有一个致命的问题，就是两个if那里，如果当前的节点是个叶子节点，它的左右两个孩子节点都是空树，而对空树解引用取它的值就会出错，所以还需要在做改进：

bool isUnivalTree(struct TreeNode* root){
    if(root == NULL)
        return true;

    if(root->left && root->val != root->left->val)
        return false;
    if(root->right && root->val != root->right->val)
        return false;

    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

8.2相同的树

原题传送门：力扣
题目：

这一题可以先判断两棵树的根节点是否相同，如果不同就返回false,如果相同就继续向下判断，这里就要用到递归，把这个问题化做成一个一个子问题，现在就是判断两棵树的左子树是否相等和右子树是否相等。

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(p->val != q->val)
        return false;

    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

这里判断的是不相等，道理和第一题一样，只有不相等你才能真正的拿到最终结果，如果相等就不管，直接向下走就行。

这里把递归的大思路写出来了，现在来找递归的终止条件也可以认为，递归到不能递归的时候的样子：
在程序运行到最后时，应该要判断两棵树是空树的情况。

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    //当p,q都为空的时候
    if(p == NULL && q == NULL)
        return true;

    //当p和q只有一个为空
    if(p == NULL || q == NULL)
        return false;

    //当p和q都不为空
    if(p->val != q->val)
        return false;

    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

空树也要分两种情况，就是两棵树同时为空的时候，这里可以把它当成是相同的，但是只有一个是空树，就肯定是错的，像下面这个：

这里左边的树虽然不是空树，但是右边的树是空树，根据这种情况，要返回false.

8.3另一棵子树

原题传送门：力扣

题目：

这题和上一题有一些些关系，因为这里要用到上一题写的代码。可以直接比较两棵树是否相同，如果相同就直接返回true，但是不相同的话，就分割成子问题，判断左/右子树与subroot是否相同：

//判断两棵树是否相同
bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    //当p,q都为空的时候
    if(p == NULL && q == NULL)
        return true;

    //当p和q只有一个为空
    if(p == NULL || q == NULL)
        return false;

    //当p和q都不为空
    if(p->val != q->val)
        return false;

    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(isSameTree(root, subRoot))
        return true;

    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

注意了，这里判断的是相同则返回，虽然和前几题返回的情况不一样，但是思路一样，因为只要判断成功就说明结果一定是正确的，如果当前的树和subroot不相等，不代表后面的子树也不想等。

还有最后的返回值是或而不是且，因为左右两棵子树只要找到一棵与subroot相等即可，只有两棵子树都找不到才返回false.

最后递归到不能递归的时候也就是树为空的时候,但是题目里说过了subroot不可能是空树：

也就是说root一直递归到空树的时候肯定找不到与subroot相同的树了，此时直接返回false.

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    //当p,q都为空的时候
    if(p == NULL && q == NULL)
        return true;

    //当p和q只有一个为空
    if(p == NULL || q == NULL)
        return false;

    //当p和q都不为空
    if(p->val != q->val)
        return false;

    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(root == NULL)
        return false;

    if(isSameTree(root, subRoot))
        return true;

    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

8.4二叉树的创建与遍历

原题传送门：牛客

题目：

这题是输入一个字符串，字符串中把#当成空树，题目要求是需要你把这个字符串自己构建成一个树然后中序打印出来。中序打印应该不难，我在前面已经将过了。这题的核心是如何将一个字符串变成一棵树。

现在先反着分析一波，一个树是怎么通过前序遍历变成一个字符串的：

前序遍历第一个找到的应该是根节点a,然后找它的左子树，把节点b当成左子树的根节点，现在第二个找到的是b，继续找b的左子树,现在把d当成子树的根节点，此时找到的就是d,目前找的顺序就是a->b->d然后找d的左子树，发现是NULL，按照题目的意思，如果是空的话应该打印#，找到第一个#的时候就可以返回了，继续找d的右子树，同样打印一个#。现在b的左子树全部找到了，开始找b的右子树，也是空同样打印#，现在的顺序是a->b->d->#->#->#.b的左右子树找完后返回，开始找a的右子树，现在把a的有孩子c当成右子树的根节点，所以先找的是c，c找完就找它的左右子树因为都是空所以返回#.

最后结果应该是：

现在开始反着推导，将一个字符串变成一棵树
这里设置一个下标i用来遍历这个字符串：

把a节点建好之后，i向后挪动一个位置，因为经过刚才通过树构建字符串来看，只有走到空树的时候才打印#然后返回，这就说明字符串指针只要没有直到#这个字符，就一直构建左节点：

走到这里的时候就不能继续向下走了，遍历到字符串的#时说明此时为空树节点的左子树已经全部找完该返回了。那现在要构建的就是d的右子树：

同样继续返回。

然后i继续向下走，当走到不是一个#的时候说明，这是一个新节点，因为之前遇到#就返回，现在这个新节点肯定是链接到a的右边：

最后两个#这里就不画了，肯定是链接在c的左右子树：

等到c的左右两个子树都返回，然后最终一直返回到a这个根节点，最后在返回这个根节点，我们就把树创建好并且把数的地址传出来。

理论这里大概讲完了，现在用代码来实践一下：

//定义树的节点
struct TreeNode
{
    char val;
    struct TreeNode* left;
    struct TreeNode* right;
};

//创建树
struct TreeNode* TreeCreat (char* str, int* i)
{
    if(str[*i] == '#')
    {
        (*i)++;
        return NULL;
    }
    
	//新节点
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));

    root->val = str[(*i)++];
    root->left = TreeCreat(str, i);
    root->right = TreeCreat(str, i);

    return root;
}

刚开始判断是不是#，如果是，说明此时是空树。跟之前学到的递归一样，但如果不是#，说明此时应该创建一个新的节点，这里用malloc开辟。然后把字符串里的值传进去，然后继续向左和右递归。因为这里的函数的作用是创建一棵数嘛，这里把函数的返回值连接到当前节点的左，右两个指针上就行了。

像这样一直递归，一直递归，找到#就返回，最终返回根节点的地址。根据一个字符串构建一棵树就完成了。

这里还要注意一个点，就是i这个变量，注意看我这里传进来的是一个指针，有人可能会问，i这个变量不是代表着数组下标吗，这个下标的类型为什么是个指针？其实是因为如果你只是简简单单的传个整型变量的话，函数一直递归在返回的时候，可能i指向字符串的位置就不是我们希望的那个位置了，这里我画个图简单了解一下：

此时一直向下递归着走，没往后走一步i都会++，现在看还是一点问题都没有的，但是找到#应该要返回，但是返回的时候就要出问题了：

看上面这图，在返回到b这个节点然后找b的右子树时，现在字符串下标i应该向后走一步，也就是说b右边的这个#应该对应的下标是3的位置，但是我们因为没有真正改变i的值，此时i的值应该是当前函数i的值加1，而当前i的值上面已经标出来是1了。这样就出问题了。虽然这里i的值2，3都是#，但不代表后面不会出错。

所以这里传进来的是i这个值的指针，你每向后走一步，都能保证+的都是同一个i。

创建二叉树已经写完了，现在我在通过画图的方式加深一下理解：

现在通过向下递归，已经创建好了三个节点，但是现在还没把这些节点连起来，继续：

通过上图发现继续向下走已经到空节点了，这样就返回一个空并且把这两个空都叫给当前节点也就是d的左右两边，像这样：

然后我们继续向下走：

返回到d这个节点的时候，节点是d的这个函数该返回了，返回的值就是d这个节点的地址，而返回的位置恰好是b这个节点的左指针指向的位置，这样我们是不是把b的左数全部创建好并连接起来了？像这样：

后面的图就不好了，基本情况在这里我已经画好了，根据图可以看到，通过向下递归，把需要创建的节点创建好，然后返回的时候再一个一个连起来，这样一棵树就建完了。

再回到题目这里来，后面的就没什么难度了，直接看代码：

#include <stdio.h>
#include <stdlib.h>

struct TreeNode
{
    char val;
    struct TreeNode* left;
    struct TreeNode* right;
};

//创建树
struct TreeNode* TreeCreat (char* str, int* i)
{
    if(str[*i] == '#')
    {
        (*i)++;
        return NULL;
    }

    //如果不是空就创建一个新节点
    struct TreeNode* root = 
        (struct TreeNode*)malloc(sizeof(struct TreeNode));

    root->val = str[(*i)++];
    root->left = TreeCreat(str, i);
    root->right = TreeCreat(str, i);

    return root;
}

//中序遍历
void MidOrder(struct TreeNode* root)
{
    if(root == NULL)
        return;

    MidOrder(root->left);
    printf("%c ", root->val);
    MidOrder(root->right);
}

int main() {
    char str[101];
    scanf("%s", str);

    int i = 0;
    //创建树
    struct TreeNode* root = TreeCreat(str, &i);

    //中序遍历
    MidOrder(root);
    return 0;
}

8.5判断是否为完全二叉树

这里需要用到之前讲过的层序遍历，现在我通过画图大致讲一下思路，先提供一棵树，判断这个树是不是完全二叉树：

首先上面这图可以当成一个完全二叉树，根据之前讲的层序遍历来走，只是稍微变化了一些，层序遍历是一个节点出队列，它的两个孩子不是空就入队列，这里不一样，不管你是不是空都入队列，先入a：

然后a出来把b,c在放进去：

b出来，d,e进去：

c出来，进去两个空：

后面也一样，d,e出来把NULL放进去：

现在就进入到这道题的核心了，首先NULL代表什么？就是空吧说明此时队列里存的内容什么都没有，看我调试的结果：

这里的size是6，头，尾两个指针都是空。
好，现在先看目前写出来的代码：

//判断是否为完全二叉树
bool TreeComplete(BTNode* root)
{
	Queue pq;
	QueueInit(&pq);

	//入队列
	QueuePush(&pq, root);

	while (!QueueEmpty(&pq))
	{
		//出队列，然后将这个节点的两个孩子传进去
		QDataType tmp = QueueFront(&pq);
		if (tmp)
		{
			QueuePop(&pq);

			QueuePush(&pq, tmp->left);
			QueuePush(&pq, tmp->right);
		}
		else
			break;
	}
	QueueDestroy(&pq);
}

等到取出的队列为空的时候，我们直接break跳出来。

等程序走到这一步的时候就可以判断：如果当前队列的头指针是空的话，我们来进行一个判断，具体怎么判断呢？我们来对比一下完全二叉树，非完全二叉树在遇到第一个空后队列里的内容：

我们发现完全二叉树后面什么都没有了，而非完全二叉树里面还有一个节点。这样我们在出队列出到一个空的时候跳出来，跳出来做一个判断：将队列此时里面的内容一直出，直到队列为空的时候停止。判断的代码可以这样写：

	while (!QueueEmpty(&pq))
	{
		QDataType tmp = QueueFront(&pq);
		QueuePop(&pq);
		if (tmp != NULL)
		{
			QueueDestroy(&pq);
			return false;
		}
	}

像这样先看看队列是不是空，如果不是就进来判断，取出一个节点看它是不是NULL，如果是就继续往后找，如果突然遇到一个节点它不是NULL，就说明这个树不是完全二叉树，此时就不用往后找了，直接返回false.如果队列都为空了，还没找到一个不是NULL的节点，说明它是一个完全二叉树，循环结束就返回true就可以了：

//判断是否为完全二叉树
bool TreeComplete(BTNode* root)
{
	Queue pq;
	QueueInit(&pq);

	//入队列
	QueuePush(&pq, root);

	while (!QueueEmpty(&pq))
	{
		//出队列，然后将这个节点的两个孩子传进去
		QDataType tmp = QueueFront(&pq);
		if (tmp)
		{
			QueuePop(&pq);

			QueuePush(&pq, tmp->left);
			QueuePush(&pq, tmp->right);
		}
		else
			break;
	}
	while (!QueueEmpty(&pq))
	{
		QDataType tmp = QueueFront(&pq);
		QueuePop(&pq);
		if (tmp != NULL)
		{
			QueueDestroy(&pq);
			return false;
		}
	}
	QueueDestroy(&pq);
	return true;
}

8.6前序遍历的题目

原题传送门：力扣

题目：

这题就是普通的前序遍历，但是我要通过这题给你们讲一些关于力扣的小细节，先看看题目给你的函数调用接口：

int* preorderTraversal(struct TreeNode* root, int* returnSize){
}

发现函数调用的参数除了树的根节点的地址，还多了一个returnSize的指针变量。这是因为题目本身不知道给你的这棵树的节点是多少，需要你自己求出来，但是不需要返回，就是说，你在函数内部假如已经求好了节点的大小，直接将returnSize解引用并将求出的大小赋值过去即可。这种写法跟8.4的写法差不多，你可以理解为，力扣在调用你写的函数之后，通过你在函数内对returnSize的值的改变，来得到当前调用的树的大小。所以在你的题目写完后要保证参数returnSize解引用的值是树的节点个数，否则会报错。

接下来看看代码：

//前序遍历
void PrevOrder(struct TreeNode* root, int* i, int* ret)
{
    if(root == NULL)
        return 0;
    
    ret[*i] = root->val;
    (*i)++;
    PrevOrder(root->left, i, ret);
    PrevOrder(root->right, i, ret);
}

//求树的节点个数
int TreeSize(struct TreeNode* root)
{
    return root == NULL ? 0 : 
        TreeSize(root->left) + TreeSize(root->right) + 1;
}


int* preorderTraversal(struct TreeNode* root, int* returnSize){
    int size = TreeSize(root);

    //为返回的数组开辟一块空间
    int* ret = (int*)malloc(sizeof(int) * size);

	//这里将returnSize实际的值改成树的节点个数
    *returnSize = size;

    int i = 0;
    //遍历
    PrevOrder(root, &i, ret);

    return ret;
}

8.7对称二叉树

原题传送门：对称二叉树

题目：

这题和判断是不是相同的树这一题有着相似的点，就是把节点的左子树和左子树相比变成了左子树和右子树相比，另一个也是一样都反过来比就行了。但是这里注意的一个小问题是之前那道题有两棵树，这里只有一棵树。但是不要紧，我们把这棵树的左右两棵子树当成两棵不同的树去比就行：

bool ComTree(struct TreeNode* root, struct TreeNode* root1)
{
    //两个都为空
    if(!root && !root1)
        return true;

    //只有一个为空
    if(!root || !root1)
        return false;

    //两个都不为空
    if(root->val != root1->val)
        return false;
    
    return ComTree(root->left, root1->right) &&
           ComTree(root->right, root1->left);
}

bool isSymmetric(struct TreeNode* root){
    return ComTree(root->left, root->right);
}

因为题目没说这棵树会不会为空树，如果想把代码写全一点，也可以加个判断：

bool isSymmetric(struct TreeNode* root){
	if(root == NULL)
	{
		return true;
	}
    return ComTree(root->left, root->right);
}

8.8根据前/后序和中序重建树

先看一个树的前，中序遍历有什么特点，比如下面这棵树：

它的前序遍历：1，2，3，4，5，6
它的中序遍历：3，2，1，5，4，6

把写的遍历和树的图对照着看：

可以发现，根据前序遍历，我们能找到这个树的根，再根据中序遍历根的位置，可以把树化成三部分：左树，根，右树

然后继续看前序遍历的下一个位置：

前序遍历找第二个根的位置，因为是前序遍历，2这个节点必然是左树的根，再看中序遍历，中序遍历的顺序是左树，根，右树，而2这个节点是根也就意味着3是2这个节点的左树：

现在再回到中序遍历，发现1的左树已经建好了，现在应该建1的右树，此时根据前序遍历红色箭头指向的应该是4这个节点，也就意味着4是右树的的根节点：

然后根据中序遍历可以判断5是左树，6是右树：

前序遍历和后序遍历差不多，只不过前序遍历找根是从前向后找，后序遍历是从后向前找。

最后再想想能不能根据前，后序建树？答案是不行，因为没有中序你即使找到了根，也找不到左/右树的位置。