网站优化需求,保定网建站模板,网络推广联系方式,辽宁建设工程信息网官网 a类业绩文章目录 前言查第K层的节点个数判断该二叉树是否为完全二叉树例题一 - Leetcode - 226反转二叉树例题一 - Leetcode - 110平衡二叉树 前言
在笔者的前几篇篇博客中介绍了二叉树的基本概念及基本实现方法#xff0c;有兴趣的朋友自己移步看看。
这篇文章主要介绍一下二叉树的… 文章目录 前言查第K层的节点个数判断该二叉树是否为完全二叉树例题一 - Leetcode - 226反转二叉树例题一 - Leetcode - 110平衡二叉树 前言
在笔者的前几篇篇博客中介绍了二叉树的基本概念及基本实现方法有兴趣的朋友自己移步看看。
这篇文章主要介绍一下二叉树的其他的几个重要功能实现方法并对几道例题进行一个分析和解答 查第K层的节点个数 就比如上图第一层有1个节点第二层2个第三次3个
这个还是比较简单的我们只需要传进去一个能够证明现在是第几层的变量然后递归左右节点为空返回NULL有值且满足层级要求返回1就可以完成了
代码如下
nt 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);
}判断该二叉树是否为完全二叉树
首先提一下满二叉树的概念即 一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是 说如果一个二叉树的层数为K且结点总数是2^k-1则它就是满二叉树。 这里与完全二叉树进行一下区分 完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K 的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。 两者的图例如下 回到判断环节我们需要用到之前说过的一个层序遍历即
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{if (root NULL) {return;}// 使用队列实现层序遍历int front 0, rear 0;BTNode** queue (BTNode**)malloc(sizeof(BTNode*) * 1000); // 假设节点数不超过1000queue[rear] root;while (front rear) {BTNode* current queue[front]; // 取出队列前端节点printf(%c , current-data);if (current-left ! NULL) {queue[rear] current-left; // 左子节点入队}if (current-right ! NULL) {queue[rear] current-right; // 右子节点入队}}free(queue); // 释放队列内存
}而这里我们需要做的就是下面两部
1、层序遍历走空也进队列 2、遇到第一个空节点时开始判断后面全空就是完全二叉树后面有非空就不是完全二叉树 比如这个图我们建立一个队列不断遍历将左右节点加入到队列中去而7的位置为空
我们通过循环判断队列是否为空每次循环出队一个头节点尾插左右节点不论是否为空
完成这步后等遇到的节点为空时退出循环开始判断这个队列是否为空因为我们在添加时加入了很多新的空值所以我们需要遍历队列里面的元素一旦遇到有元素不为空就代表空节点后还有元素就比如上图的7后面还有56一样。
代码如下
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;}}注意
因为我们之前创建的队列是通过数组建的而数组的值往往设定为int这里如果不是二外创建新的数组就像上面层序遍历那样就记得使用将队列中数组的元素设为二叉树节点的类型另外可能有朋友会认为在添入队列时堆对NULL空节点进行引用将空节点的子节点实则不会因为我们是通过循环使左右子节点加入一次仅加入两个不会因为循环过快导致上述现象 例题一 - Leetcode - 226反转二叉树
Leetcode - 226反转二叉树 这题的思路没那么复杂我们抓住他反转的本质其实就是每个节点的左右节点交换这样一来就完成了代码如下
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/typedef struct TreeNode TreeNode;
struct TreeNode* invertTree(struct TreeNode* root) {if(root NULL)return NULL;TreeNode* left invertTree(root-left);TreeNode* right invertTree(root-right);root-left right;root-right left;return root;
}值得一提的是这里我们不是先进行递归在对左右节点赋值的吗因为二叉树的本质还是一种链表是一种逻辑结构。
所以即使我们先将左右节点交换再递归下去是不会影响最终结果的比如下面这串代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
typedef struct TreeNode TreeNode;
struct TreeNode* invertTree(struct TreeNode* root) {if(root NULL){return NULL;}TreeNode* left root-left;TreeNode* right root-right;root-right left;root-left right;left invertTree(root-left);right invertTree(root-right);return root;
}例题一 - Leetcode - 110平衡二叉树
Leetcode - 110平衡二叉树
关于这道题我们需要了解一个概念即平衡二叉树 所以我们可以通过方法名来获取一个节点的深度对左右两个节点进行比较若插值不大于1即可
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
#define MAX(a,b) ((a)(b)?(a):(b))
int height(struct TreeNode* root)
{if(root NULL)return 0;return MAX(height(root-left),height(root-right))1;
}
bool isBalanced(struct TreeNode* root) {if(root NULL)return true;return (fabs(height(root-left) - height(root-right)) 1 isBalanced(root-left) isBalanced(root-right));
}于是我们可以按照思路这样写出但是这个写法存在较大缺陷就是时间复杂度太高了由于是自顶向下递归因此对于同一个节点函数 height 会被重复调用导致时间复杂度较高。如果使用自底向上的做法则对于每个节点函数 height 只会被调用一次。即
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
#define MAX(a,b) ((a)(b)?(a):(b))
int height(struct TreeNode* root)
{if(root NULL)return 0;int leftHeight height(root-left);int rightHeight height(root-right);if(leftHeight -1 || rightHeight -1 || fabs(leftHeight - rightHeight) 1){return -1;}else{return MAX(leftHeight, rightHeight) 1;}
}
bool isBalanced(str
uct TreeNode* root) {return height(root) ! -1;}
