【数据结构】手撕二叉树oj练习与经典问题

二叉树经典问题

一、结点个数

二、叶结点个数

三、第K层结点个数

965. 单值二叉树 - 力扣（LeetCode）

100. 相同的树 - 力扣（LeetCode）

101. 对称二叉树 - 力扣（LeetCode）

572. 另一棵树的子树 - 力扣（LeetCode）

二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

二叉树经典问题

一、结点个数

方法一：count计数
//节点个数
int count = 0;
void BTreeSize(BTNode* root)
{
	if (root == NULL) //如果为空
		return;
	++count;
	BTreeSize(root->left);
	BTreeSize(root->right);
}
缺点在于会有多线程安全问题，如果几个程序同时调用会发生错乱

方法二：遍历+传址计数
//节点个数
void BTreeSize(BTNode* root, int* pCount)
{
	if (root == NULL) //如果为空
		return;
	++(*pCount);
	BTreeSize(root->left, pCount);
	BTreeSize(root->right, pCount);
}
传地址解决多线程问题，但是每次计数都要重置count为0，代码不美观

方法三：

直接利用子问题的思想来写，返回当root为空则0，不是就递归左树+右树+1。

空树，最小规模子问题，结点个数返回0
非空，左子树结点个数+右子树结点个数 + 1（自己）
int BTreeSize(BTNode* root)
{
	return root == NULL ? 0 : 
    BTreeSize(root->left) + 
    BTreeSize(root->right) + 1;
}
总结：

上述算法思想其实就是分治思想。

把复杂的问题分成更小规模的子问题，子问题再分成更小规模的子问题……直到子问题不可再分割，直接能出结果。

二、叶结点个数

思路1：遍历+计数

在遍历的基础上如果结点的左右子树均为空则count++。但是此题我们依旧采用分治思想

思路2：分治思想

首先，如果为空，直接返回0，如若结点的左子树和右子树均为空，则为叶节点，此时返回1，其它的继续分治递归。

代码演示：
//叶结点个数
int BTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0; //为空，返回0
	if (root->left == NULL && root->right == NULL)
		return 1; //如果左右子树均为空，则为叶结点，返回1
	return BTreeLeafSize(root->left) + BTreeLeafSize(root->right); //继续分治递归
}

三、第K层结点个数

思路：

假设K=3

空树，返回0
非空，且K == 1，返回1
非空，且K>1，转换成左子树K-1层节点个数 + 右子树K-1层节点个数

代码演示：
//第K层节点个数,K>=1
int BTreeKLevelSize(BTNode* root, int k)
{
	assert(k >= 1);
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BTreeKLevelSize(root->left, k - 1) + BTreeKLevelSize(root->right, k - 1);
}

四、二叉树的深度

思路：

此题同样是运用分治的思想来解决，要比较左子树的高度和右子树的高度，大的那个就+1，因为还有根结点也算1个高度。

代码演示：
//求树的深度
int BTreeDepth(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftDepth = BTreeDepth(root->left); //左子树高度
	int rightDepth = BTreeDepth(root->right);//右子树高度
	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

五、二叉树查找值为x的节点

思路：

还是利用分治的思想，将其递归化成子问题去解决

先去根结点寻找，是就返回此节点
此时去左子树查找有无节点x
最后再去右子数去查找有无节点x
若左右子树均找不到节点x，直接返回空

代码演示：


//二叉树查找值为x的节点
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
	//如果根节点为空，直接返回空
	if (root == NULL)
		return NULL;
	//如果找到节点，直接返回节点位置
	if (root->data == x)
		return root;
	//若没找到，去左子树找
	BTNode* ret1 = BTreeFind(root->left, x);
	if (ret1)
		return ret1;
	//此时左子树没找到，去右子树找
	BTNode* ret2 = BTreeFind(root->right, x);
	if (ret2)
		return ret2;
	//若左子树和右子树都每找到，直接返回空
	return NULL;
}

测试：


#include
#include
#include 
using namespace std;
 
//创建二叉链结构
typedef int BTDataType; //本文以int整型为例
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	int data;
}BTNode;
//创建结点
BTNode* BuyBTNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	node->data = x;
	node->left = node->right = NULL;
	return node;
}
//构建树
BTNode* CreatBinaryTree()
{
	//创建6个结点
	BTNode* node1 = BuyBTNode(1);
	BTNode* node2 = BuyBTNode(2);
	BTNode* node3 = BuyBTNode(3);
	BTNode* node4 = BuyBTNode(4);
	BTNode* node5 = BuyBTNode(5);
	BTNode* node6 = BuyBTNode(6);
	//将结点连接起来，构成自己想要的树
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	//返回根结点
	return node1;
}
//二叉树查找值为x的节点
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
	//如果根节点为空，直接返回空
	if (root == NULL)
		return NULL;
	//如果找到节点，直接返回节点位置
	if (root->data == x)
		return root;
	//若没找到，去左子树找
	BTNode* ret1 = BTreeFind(root->left, x);
	if (ret1)
		return ret1;
	//此时左子树没找到，去右子树找
	BTNode* ret2 = BTreeFind(root->right, x);
	if (ret2)
		return ret2;
	//若左子树和右子树都每找到，直接返回空
	return NULL;
}
 
int main()
{
	BTNode* tree = CreatBinaryTree();
	for (int i = 0; i <= 7; i++)
	{
		printf("Find:%d,%p\n", i, BTreeFind(tree, i));
	}
	return 0;
}

六、二叉树的销毁

思路：

销毁的思想和遍历类似，如若我挨个遍历的同时，没遍历一次就销毁一次，岂不能达到效果，但是又会存在一个问题，那就是你要采用什么样的遍历方式？倘若你采用前序遍历，刚开始就把根销毁了，那么后面的子树还怎么销毁呢？因为此时根没了，子树找不到了就，所以要采用倒着销毁的规则，也就是后续的思想
代码演示：
//二叉树的销毁
void BTreeDestory(BTNode* root)
{
	if (root == NULL)
		return;
	BTreeDestory(root->left);
	BTreeDestory(root->right);
	free(root);
	root = NULL;
}

七、判断二叉树是否是完全二叉树

完全二叉树的概念：前k-1层是满的，最后一层是连续的。

思路：层序遍历+变形

通过上图，不难发现，如果是完全二叉树的话，在层序遍历的时候是不会出现间隔的NULL。例如第一幅图就不是完全二叉树，因为层序遍历到第三层的时候会出现间隔NULL，因为3 -> NULL -> 5 -> 6，而剩余两幅图均不会出现这样的问题，接下来，我将利用类似的思想解决这道题。

层序遍历明确指出，当其中一个结点pop出来时，要把它的孩子给push进队列里，但前提是把不为空的孩子给push进去，现在规矩变了，不管你是否为空，都给push进去，也就是说出一个结点，push两个孩子结点，使其停止的条件是当我pop出来的结点为NULL时，此时停止push，一直pop到队列为空，如果全是空，就是完全二叉树，如果有非空，就不是。

总结

层序遍历，空节点也进队列
出到空节点以后，出队列中所有数据，如果全是空，就是完全二叉树，如果有非空，就不是

图示：

代码演示：
//判断一颗二叉树是否是完全二叉树
bool BTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root); //根结点不为空，入队列
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q); //删除队头数据，方便后续取队头数据
		if (front == NULL) //如果取队头为空，停止，接下来进入下一个while循环判断是否为完全二叉树
			break;
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q); 
		//如果空出到非空，那么说明不是完全二叉树
		if (front)
		{
			QueueDestory(&q);
			return false;
		}
	}
	QueueDestory(&q);
	return true; //全是空，此时返回true，为完全二叉树
}

二叉树OJ练习

965. 单值二叉树 - 力扣（LeetCode）

思路：

如果每个根和其左右孩子都相等，那么我们就可以断定此二叉树必是单值二叉树，因为根节点也会成为孩子，孩子也会成为根结点，所以采用分治思想


bool isUnivalTree(struct TreeNode* root) {
    if (root == NULL)
    {
        return true; //如果为空树，同样符合单值，直接返回true
    }
    if (root->left && root->left->val != root->val)
    {
        return false;//如果左孩子存在并且左孩子和根结点不同，返回false
    }
    if (root->right && root->right->val != root->val)
    {
        return false;//如果右孩子存在并且右孩子和根结点不同，返回false
    }
    return isUnivalTree(root->left) && isUnivalTree(root->right);//递归+分治，转化子问题
}

100. 相同的树 - 力扣（LeetCode）

思路：

非常简单，要先排除些特殊情况，如若两棵树的根节点均为空，那么符合题意，如若有任何一棵树先为空，那么同样不符合，其次就是判断节点值是否相等，最后就是最基本的递归（递归左子树和右子树）+分治即可解决此问题。


bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    //都是空树
    if (p == NULL && q == NULL)
    {
        return true; //如果p和q均为NULL，成立，返回true
    }
    //一个为空，一个不为空
    if (p == NULL || q == NULL)
    {
        return false; //若p和q其中一个先为空，那么不相同，返回false
    }
    //都不为空
    if (p->val != q->val)
    {
        return false; //如果对应子树的值不同，同样返回false
    }
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);//分治+递归
}

顺便击败了全世界的人，哈哈哈

101. 对称二叉树 - 力扣（LeetCode）

思路：

因为是对称，所以左子树的右树与右子树的左树相同，利用辅助函数传左右子树，然后利用上题代码判断左子树的右树与右子树的左树是否相同（再在主函数使用递归+分治的思想转换成子问题继续比较其余的节点）


 //辅助函数比较对称的值是否相等
bool _isSymmetric(struct TreeNode* p, struct TreeNode* q) {
    if (p == NULL & q == NULL)
    {
        return true; //如果p和q均为NULL，成立，返回true
    }
    if (p == NULL || q == NULL)
    {
        return false; //若p和q其中一个先为空，那么不相同，返回false
    }
    if (p->val != q->val)
    {
        return false; //如果对应子树的值不同，同样返回false
    }
    return _isSymmetric(p->left, q->right) && _isSymmetric(p->right, q->left);//分治+递归
}
bool isSymmetric(struct TreeNode* root) {
    if (root == NULL)
    {
        return true;
    }
    return _isSymmetric(root->left, root->right);
}

572. 另一棵树的子树 - 力扣（LeetCode）

思路：

遍历左边的树的每一个结点，作子树的根，跟右边的子树都比较一下，此时我们就可以单独封装一个先前写过的函数isSameTree，用来比较两棵树是否相同，依次比较，若是子树，返回true


//辅助函数，专门判断两棵树是否相同
bool isSameTree(struct TreeNode* root, struct TreeNode* subRoot)
{
    if (root == NULL && subRoot == NULL)
    {
        return true;
    }
    if (root == NULL || subRoot == NULL)
    {
        return false;
    }
    if (root->val != subRoot->val)
    {
        return false;
    }
    return isSameTree(root->left, subRoot->left) && isSameTree(root->right, subRoot->right);
}
 
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    if (root == NULL)
    {
        return false; //根都为空了，何来子树，直接返回false
    }
    if (isSameTree(root, subRoot))
    {
        return true; //是子树就返回true
    }
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

思路:

题目中还有一个要求，在根据字符串创建树时是按照先序的遍历方式创建的，也就是根->左子树->右子树
首先遇到a，不是#，继续往下构建左子树b，再往下构建左子树c，再递归构建c的左子树为#，也就是空，此时递归c的右子树#为空，递归回来链到b的右子树d，继续构建d的左子树e，构建e的左子树#为空，递归返回构建e的右子树g，再递归g的左右子树均为空，递归返回d的右子树f，构建f的左右子树均为#空，递归返回a的右子树#为空，至此构建树结束

如图：

当我们创建好二叉树的结构后，只需要将其按照题意中序遍历的方式打印出来即可


#include
//创建二叉树结构
typedef struct BinaryTreeNode
{
    char data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTNode;
//创捷结点，先序结构创建
BTNode* CreateTree(char* a, int* pi)
{
    if (a[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
 
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    root->data = a[(*pi)++];
 
    root->left = CreateTree(a, pi);
    root->right = CreateTree(a, pi);
    return root;
}
 
void InOrder(BTNode* root)
{
    if (root == NULL)
        return;
    InOrder(root->left);
    printf("%c ", root->data);
    InOrder(root->right);
}
 
int main()
{
    char a[100];
    scanf("%s", a);
    int i = 0;
    BTNode* tree = CreateTree(a, &i);
    InOrder(tree);
    return 0;
}

相关阅读:
【瑞吉外卖】day07：新增套餐、套餐分页查询、删除套餐
 javaweb：mybatis：mapper(sql映射+代理开发+配置文件之设置别名、多环境配置、顺序+注解开发）
vivado 高级编程功能1
openldap-sasl身份认证镜像
 【Python数据科学快速入门系列 | 02】创建ndarray对象的十多种方法
 nc65单据穿透
 基于Keil a51汇编 —— 控制语句
 STM32-NUCLEO-F411RE-USART_串口
 Qt-qrencode开发-生成、显示二维码
 索尼 toio™ 应用创意开发征文｜小巧机器，大无限，探索奇妙世界
原文地址：https://blog.csdn.net/qq_61386381/article/details/125972287

【数据结构】手撕二叉树oj练习与经典问题

二叉树经典问题

一、结点个数

二、 叶结点个数

三、 第K层结点个数

四、二叉树的深度

五、 二叉树查找值为x的节点

六、二叉树的销毁

七、 判断二叉树是否是完全二叉树

二叉树OJ练习

965. 单值二叉树 - 力扣（LeetCode）

100. 相同的树 - 力扣（LeetCode）

101. 对称二叉树 - 力扣（LeetCode）

572. 另一棵树的子树 - 力扣（LeetCode）

二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

二、叶结点个数

三、第K层结点个数

五、二叉树查找值为x的节点

七、判断二叉树是否是完全二叉树