落叶归根：递归思想在二叉树叶子节点类问题中的妙用

鸽芷咕

发布于 2023-12-25 15:17:56

800

发布于 2023-12-25 15:17:56

文章被收录于专栏：C++干货基地C++干货基地

🎬 鸽芷咕：个人主页 🔥 个人专栏: 《linux深造日志》《高效算法》

⛺️生活的理想，就是为了理想的生活!

文章目录

一、递归的介绍
二、递归算法的妙用
- 2.1 二叉树结点个数
- 2.2 二叉树叶子结点个数
- 2.3 二叉树第k层结点个数
- 2.4 二叉树查找值为x的结点
📝文章结语：

一、递归的介绍

递归算法的理解一直都是是比较抽象的，但不可否认他是一个高效且简单的算法。几行代码就可以解决递归一些复杂的思想：

其思想就是通过一个大问题分解成更小、相似的子问题
来进行重复调用去解决复杂的大问题

而递归算法在使用的时候一定要注意好，递归的结束条件和递归的基本条件

一但结束条件没控制到就会发生死递归这类的程序错误
而基本递归情况是一个中最关键的部分，否则就会出现栈溢出等情况

二、递归算法的妙用

2.1 二叉树结点个数

哦豁，是不是没想到一行代码就解决了求二叉树结点个数的问题。哈哈哈递归算法就是如此的简单

大问题转换为小问题
递归结束条件

// 二叉树结点个数
int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

2.2 二叉树叶子结点个数

📚 代码演示：

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

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

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

2.3 二叉树第k层结点个数

第k层结点个数，这个就有点难度了，不过其实还好因为他们给我了我们节点的层数当我们递归一次的时候：

节点进行-1，来表示我们当前的层数当他为1时就递归到我们需要的层数了
🔥 注：一定要注意好不要自减这样就把原本的k给改变了

📚 代码演示：

// 二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}

	if (k == 1 && root != NULL)
	{
		return 1;
	}

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

2.4 二叉树查找值为x的结点

查找值为x的节点首先我们需要判断跟为空的情况再来对他的左右子树进行递归查找：

这里要注意的是递归返回的值是上一层的值，一旦不进行接收那么返回值就会出现问题

// 二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;

	if (root->data == x)
	{
		return root;
	}

	BTNode* find = NULL;
	find = BinaryTreeFind(root->left, x);
	if (find)
		return find;

	find = BinaryTreeFind(root->right, x);
	if (find)
		return find;

	return NULL;
}

📝文章结语：

☁️ 把本章的内容全部掌握，铁汁们就可以熟练应用switch语句啦！ 看到这里了还不给博主扣个： ⛳️ 点赞🍹收藏 ⭐️ 关注！ 💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖 拜托拜托这个真的很重要！ 你们的点赞就是博主更新最大的动力！ 有问题可以评论或者私信呢秒回哦。