【二叉树经典习题讲解】

If you find a path with no obstacles, probably doesn't lead anywhere.

1 前中后序遍历一颗二叉树

2 总的结点个数

3 求叶子节点个数

4 求树的高度

5 第k层结点个数

6 二叉树的层序遍历

7 判断一棵树是否为完全二叉树

1 二叉树的前序遍历

2 单值二叉树

3 翻转二叉树

4 相同的树

5 对称二叉树

6 另一颗树的子树

7 二叉树的构建和遍历

刚开始我们来回顾练习一下比较基础的求解二叉树的一些问题：像前（中，后）序遍历一颗二叉树，求总的结点个数，求叶子结点个数，树的高度等等。

1 前中后序遍历一颗二叉树

代码实现：

void PrevOrder(BTNode* root)
{if (root == NULL){printf("NULL ");//可加可不加，加了更好理解return;}printf("%d ", root->val);PrevOrder(root->left);PrevOrder(root->right);
}void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");//可加可不加，加了更好理解return;}InOrder(root->left);printf("%d ", root->val);InOrder(root->right);
}void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");//可加可不加，加了更好理解return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->val);
}

2 总的结点个数

具体代码：

int TreeNodeSize(BTNode* root)
{return root == NULL ? 0 : TreeNodeSize(root->left) + TreeNodeSize(root->right) + 1;
}

3 求叶子节点个数

具体代码：

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);
}

4 求树的高度

具体代码：

int TreeHeight(BTNode* root)
{//方法1：//if (root == NULL)//	return 0;//0不能省略//return TreeHeight(root->left) > TreeHeight(root->right) ? TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1;//缺陷：函数递归被重复调用次数过多，效率低下，不可取//改进方法:if (root == NULL)return 0;int leftH = TreeHeight(root->left);int rightH = TreeHeight(root->right);return leftH > rightH ? leftH + 1 : rightH + 1;
}

5 第k层结点个数

具体代码：

int TreeKLevelSize(BTNode* root,int k)
{if (root == NULL)return 0;if (1 == k)return 1;return TreeKLevelSize(root->left, k - 1) + TreeKLevelSize(root->right, k - 1);
}

6 二叉树的层序遍历

解题思路：用队列存储二叉树的根节点，pop根节点之前将不为空的孩子继续入队列，直到队列为空。

具体代码：

void TreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->val);if (front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}
}

7 判断一棵树是否为完全二叉树

解题思路：很显然用节点个数是无法判断出一棵树是否为完全二叉树的。判断一棵树是否为完全二叉树的最关键步骤是是否这棵树连续，比较好一种方法是利用层序遍历来处理，将根节点的孩子都入队，不管是否为空，遇到空就跳出来，然后检查后面是否有非空。

具体代码：

bool isCompleteTree(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);if (!front)break;//遇到空就跳出来QueuePop(&q);QueuePush(&q, front->left);QueuePush(&q, front->right);}//判断后面是否还有非空while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);if (front){QueueDestroy(&q);return false;}QueuePop(&q);}QueueDestroy(&q);return true;
}

接下来就是力扣或者牛客上的OJ:

1 二叉树的前序遍历

解题思路：等等，这道题不是之前讲过了吗？之前讲过是没错，不过在力扣上这道题要求你将前序遍历的结果返回到一个数组中然后返回，具体实现上要稍微麻烦一些。

具体代码：

int TreeSize(struct TreeNode* root){return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;}void _PrevOrder(struct TreeNode* root,int* pi,int* a){if(!root)return ;a[(*pi)++]=root->val;_PrevOrder(root->left,pi,a);_PrevOrder(root->right,pi,a);}int* preorderTraversal(struct TreeNode* root, int* returnSize){
int sz=TreeSize(root);
int* a=(int*)malloc(sizeof(int)*sz);int i=0;
_PrevOrder(root,&i,a);
* returnSize=sz;
return a;
}

2 单值二叉树

解题思路：我们知道如果当前根为空，就可以暂时认为返回结果是true（并不能确定整棵树的情况），但是只要根与左孩子或者右孩子只要有一个不相等的话就可以返回false,然后再不断递归下去，具体实现代码方式有两种，大家可以自行选择。

具体代码：

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

3 翻转二叉树

具体代码：

struct TreeNode* invertTree(struct TreeNode* root){if(!root)return NULL;
struct TreeNode* left=invertTree(root->left);
struct TreeNode* right=invertTree(root->right);
root->left=right;
root->right=left;
return root;
}

4 相同的树

具体代码：

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
if(p==NULL && q==NULL)return true;
else if(p==NULL || q==NULL)return false;
else if(p->val != q->val)return false;
return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

5 对称二叉树

解题思路：有点儿类似与相同的树的解题思路，设置一个check函数帮助我们判断左右子树是否相等。

具体代码：

bool check(struct TreeNode* p,struct TreeNode* q)
{
if(!p && !q)return true;
if(!p || !q)return false;
return p->val == q->val && check(p->left,q->right) && check(p->right,q->left);
}bool isSymmetric(struct TreeNode* root){
return check(root,root);
}

6 另一颗树的子树

解题思路：将该树的每一颗子树与要比较的树比较是否相等，若有一棵树相等，就返回true,全都不相等就返回false.

具体代码：

bool isSame(struct TreeNode* p, struct TreeNode* q)
{
if(!p && !q)return true;
if(!p || !q)return false;
if(p->val != q->val)return false;
return isSame(p->left,q->left) && isSame(p->right,q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
if(!root)return false;
if(isSame(root,subRoot))return true;
return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}

7 二叉树的构建和遍历

解题思路：与在力扣上的题不同，牛客上的题大都是IO型的，所以需要我们自己输入输出，有了前面的那些例子，构建这颗二叉树也不算太难，唯一需要注意的就是构建时传入的是i的地址，因为后面数据都是要不断迭代走的。

具体代码：

#include <stdio.h>
#include<stdlib.h>
typedef struct BinaryTree {char val;struct BinaryTree* left;struct BinaryTree* right;
} BT;BT* PrevCreat(char* str, int* pi) {if (str[*pi] == '#') {(*pi)++;return NULL;}BT* root = (BT*)malloc(sizeof(BT));root->val = str[(*pi)++];root->left = PrevCreat(str, pi);root->right = PrevCreat(str, pi);return root;
}void InOrder (BT* root) {if (!root)return;InOrder(root->left);printf("%c ", root->val);InOrder(root->right);
}int main() {char str[101];scanf("%s", str);int i = 0;BT* root = PrevCreat(str, &i);InOrder(root);return 0;
}