由浅入深二叉树刷题指南与讲解

前言

上一篇我们已经了解了二叉树的实现方式, 那么本篇重在进入二叉树OJ刷题环节, 我也会分享我在写题的思路, 帮助我们更好的理解二叉树, 并且本篇也进行二叉树其他方法的实现, 也欢迎不同观点评论区留言.

博客主页: 酷酷学!!!
创作不易, 感谢关注~

二叉树OJ基础题目

1. 单值二叉树

题目链接: 单值二叉树

题目描述:

题目分析:

首先此题是要求判断一棵二叉树是否为单值二叉树, 也就是说每一个结点的值是否都相等, 因为二叉树递归定义的, 所以这里我们也可以采用递归的思路去解题, 二叉树可以分为根和子树, 可以判断根和子树是否相等, 然后递归进行判断子树的根和子树是否相等. 如果相等就继续下一层递归, 如果不相等就直接返回false.

判断条件是如果一颗树的左子树存在且值和根不相等, 或者右子树存在且根和右子树的值不相等, 则返回false, 如果判断到的子树为NULL,则说明其他子树都与根结点相同.

代码如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
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);
}

2. 检查两棵树是否相同

题目链接: 相同的树

题目描述:

代码如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if(p == NULL && q == NULL)
    {
        return true;
    }
    if(p == NULL || q == NULL)
    {
        return false;
    }
    if(p->val != q->val)
    {
        return false;
    }
    return isSameTree(p->left,q->left) && 
    isSameTree(p->right,q->right);
}

代码分析:

递归比较子树的根结点是否相同, 如果两个根都为空, 则表示已经比较到叶子节点的下一层, 则其它结点都比较完毕, 说明相同, 如果一个结点为NULL,另一个不为NULL,则一定不相同, 然后比较根节点是否相同, 不相同返回false,相同则继续递归比较.子树的左树和右树都相同, 则说明两棵树相同.

3. 二叉树的前中后序遍历

题目链接:

前序遍历
中序遍历
后序遍历

这里以前序遍历做讲解, 其他遍历题目解题方法类似

题目描述:

代码如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

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

void PrevOrder(struct TreeNode* root,int* arr,int* i)
{
    if(root==NULL)
    {
        return;
    }
    arr[*i] = root->val;
    (*i)++;
    PrevOrder(root->left,arr,i);
    PrevOrder(root->right,arr,i);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = TreeSize(root);
    int* arr = (int*)malloc(sizeof(int)*(*returnSize));
    int i = 0;
    PrevOrder(root,arr,&i);
    return arr;
}

代码解析:

首先*returnSize表示的是数组元素的个数, 这里传递过来的是一个指针类型变量, 因为函数外面可能会用到这个值, 想要改变只能传递实参, 题目要求遍历的结果存放在数组中, 因为我们不知道开辟多大空间, 所以可以先求一下结点个数, 也比较简单, 然后用returnSIze接收一下, 接着创建数组, 进行前序遍历, 需要另外定义一个函数, 因为遍历二叉树需要递归, 所以不可以直接递归函数, 因为不能每次都开辟一个数组, 递归结构存放在数组中, 然后返回数组即可.

4. 另一棵树的子树

题目链接: 另一棵树的子树

题目描述:

代码如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool isSameTree(struct TreeNode* p,struct TreeNode* q)
{
    if(p==NULL && q==NULL)
    {
        return true;
    }
    if(p==NULL || q==NULL)
    {
        return false;
    }
    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);
}

代码分析:

判断一棵树是否是另一棵树的子树, 也就是root的子树是否和subroot相同, 我们只需判断每一棵root的子树和subroot相同即可, 这里我们用到了上面写的代码, 判断两棵树是否相同, 这里我们需要依次去递归调用左子树和右子树与subroot进行判断, 只要有一棵树相同就说明为另一棵树的子树, 如果判断到NULL了,则说明遍历了所有子树的根都无法找到与之相同的树, 则不为另一棵树的子树.

5. 对称二叉树

题目链接: 对称二叉树

题目描述:

代码如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool _isSameTree(struct TreeNode* left,struct TreeNode* right)
{
    if(left == NULL && right == NULL)
    {
        return true;
    }
    if(left == NULL || right == NULL)
    {
        return false;
    }
    if(left->val != right->val)
    {
        return false;
    }
    return _isSameTree(left->left,right->right)
    &&_isSameTree(left->right,right->left);

}


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

代码解析:

对称二叉树, 则就是比较这棵树的两个子树, 左子树的左孩子是否和右子树的有孩子是否相同, 左子树的右孩子是否和右子树的左孩子相同, 我们可以使用判断两个相同的树的代码进行改写, 只不过传递参数不同.

6. 二叉树的构建以及遍历

题目链接: 二叉树的构建以及遍历

题目描述:

代码如下:

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

typedef char Datatype;
typedef struct BTnode
{
    struct BTnode* left;
    struct BTnode* right;
    Datatype val;
}BTnode;

BTnode* CreateTree(char* str,int* pi)
{
    if(str[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    BTnode* newnode = (BTnode*)malloc(sizeof(BTnode));
    newnode->val = str[*pi];
    (*pi)++;
    newnode->left = CreateTree(str,pi);
    newnode->right = CreateTree(str, pi);
    return newnode;
}

void InOrder(BTnode* root)
{
    if(root == NULL)
    {
        return;
    }
    InOrder(root->left);
    printf("%c ",root->val);
    InOrder(root->right);
}

int main() {
    char str[100] = {0};
    scanf("%s",str);
    int i = 0;
    BTnode* root = CreateTree(str,&i); 
    InOrder(root);
    return 0;
}

代码分析:

首先题目给定一个字符串, 这个字符串是先序遍历的, 需要我们创建一个二叉树, 然后中序遍历输出, 首先我们读取输入到的字符串到字符数组中, 然后创建二叉树, 使用递归进行创建, 定义一个树的结点, 每次申请一个结点, 如果读取到’#'则跳过, 进行下一次读取, 然后存到val中, 依次创建左子树右子树, 最后中序遍历并且打印.

二叉树其他方法的实现

1. 二叉树的销毁

这里销毁一棵二叉树肯定要先从子树进行销毁, 不然销毁了根, 就无法找到子树的结点, 递归进行销毁操作, 代码如下

void BinaryTreeDestory(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}

2. 层序遍历

所谓层序遍历就是一层一层的输出, 如下图这棵树, 层序遍历的结果为1 2 3 4 5 6, 这里层序遍历, 我们可以创建一个队列, 存放树的指针, 先让根节点入队列, 每次出队列, 若孩子结点不为空, 则入队, 队列为空, 则所有结点都出队列完毕, 出队列并且打印对头元素指向的树的值

代码如下:

void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		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);
		}
	}
	QueueDestroy(&q);
}

3. 判断二叉树是否是完全二叉树

这里我们走层序遍历, 因为层序遍历二叉树, 非空和空一定都是连续的, 这里我们不管空还是非空结点都入队列, 如果出队列到第一个NULL,则说明所有结点都以及入队列, 包括其孩子结点, 然后开始判断, 后面是否全是空, 是空则是完全二叉树, 不是空则不是完全二叉树.

代码如下:

bool TreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* Front = QueueFront(&q);
		QueuePop(&q);
	
		if (Front == NULL)
		{
			break;
		}
		QueuePush(&q, Front->left);

		QueuePush(&q, Front->right);

	}
	while (!QueueEmpty(&q))
	{
		BTNode* Front = QueueFront(&q);
		QueuePop(&q);
		if (Front)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

二叉树的其他性质

其中性质3我们可以来分析一下, 一棵树初始状态 n0表示度为0的结点, n1表示度为1的结点, n2表示度为2的结点, 初始时为一个节点, 则n0 = 1 , n2 = 0, 增加结点, 向下插入, 每增加一个度为1的结点, 度为1的结点一定是由一个度为0的结点变过来的, 增加一个度为0, 减少一个度为0 ,则只是影响了度为1的结点, 增加一个度为2的结点,则度为1的结点变成度为2的结点, 一等增加一个度为0的结点, 减少一个度为1的结点, 依次只有增加一个度为2的结点才会影响度为0的结点个数, 并且一直保持初始状态.

总结

本篇旨在介绍二叉树初学者刷题题目讲解与接上篇二叉树其他方法的实现, 以及二叉树其他性质, 如果此文有帮助, 创作不易, 感谢关注.