💛 前情提要💛
本章节是数据结构的二叉树重要面试OJ题的相关知识~
接下来我们即将进入一个全新的空间,对代码有一个全新的视角~
以下的内容一定会让你对数据结构有一个颠覆性的认识哦!!!
❗以下内容以C语言的方式实现,对于数据结构来说最重要的是思想哦❗
以下内容干货满满,跟上步伐吧~
💡本章重点二叉树的层序遍历
二叉树重要面试OJ题
🔥算法思想
🍞一.广度优先遍历🥐Ⅰ.层序遍历💡广度优先遍历: 对于二叉树来说又称为层序遍历
即访问顺序不同与先序、中序、后序遍历【这三种遍历统称为:深度优先遍历】要递归访问完一个分支后才返回再递归访问剩下的分支而层序遍历就是一层一层的遍历树的结点,遍历完一层后,才遍历下一层,直至遍历完整棵树❗特别注意:
对于广度优先遍历,我们一般借助队列的数据结构去实现【对于>队列head = pq->tail = NULL;}void QueueDestroy(Queue* pq){assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;}void QueuePush(Queue* pq, QDataType x){assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){printf("malloc fail\n");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}}void QueuePop(Queue* pq){assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}}QDataType QueueFront(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->head->data;}QDataType QueueBack(Queue* pq){assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;}bool QueueEmpty(Queue* pq){assert(pq);return pq->head == NULL;}int QueueSize(Queue* pq){assert(pq);QNode* cur = pq->head;int size = 0;while (cur){++size;cur = cur->next;}return size;}
2️⃣实现层序遍历:
void TreeLevelOrder(BTNode* root){Queue q;QueueInit(&q);if (root){QueuePush(&q, root);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->data);if (front->left != NULL){QueuePush(&q, front->left);}if (front->right != NULL){QueuePush(&q, front->right);}}QueueDestroy(&q);} 🥯Ⅱ.总结✨综上:就是层序遍历啦~
➡️相信大家对新的遍历方式有不一样的看法了吧🧡
🍞二.二叉树重要面试OJ题🔥秒杀模板❗ 秒杀口诀:
左右子树之间的逻辑关系➕树的遍历方式❓忘记的同学可以>点击网站跳转left) + treeSize(root->right) + 1;}void preorder(struct TreeNode* root, int*arr, int* i){//前序遍历if (root == NULL){return;}arr[(*i)++] = root->val;preorder(root->left, arr, i);preorder(root->right, arr, i);}int* preorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize = treeSize(root);int* arr = (int*)malloc(sizeof(int)*(*returnSize));int i = 0;preorder(root, arr, &i);return arr;}
➡️补充:
我们需要带着自己开辟的数组和数组下标进行前序遍历,因为需要将遍历得到的结点存入数组中
所以每一次下标的改变都需要让不同的递归栈帧知道,所以下标需要传的是地址(否则如果传的是下标的临时拷贝,那数组内的结点之间就会造成覆盖)
🏷️ 另一棵树的子树【难度:简单】:mag:题目传送门:
Leetcode:572. 另一棵树的子树给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树
示例 1:
输入:root = [3,4,5,1,2], subRoot = [4,1,2]输出:true示例 2:
输入:root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]输出:false💡解题关键:
遍历主树的每一个结点,让每一个结点当作根节点时,去判断此时的根节点的树是否与子树相同
此时我们便可以复用检查两棵树是否相同的代码进行判断
👉秒杀分析:
因为需要遍历主树的每一个结点,让其每一个结点当根节点时的树去与子树判断是否相同
所以我们对主树采取前序遍历【即这样遍历下,我们可以快速且从上往下全面的判断是否为子树】,若为其余遍历方式,则可能一开始就错过导致程序做了一些无用功
又因为只要主树里一旦找到为子树的情况,就无需继续找子树了,所以逻辑关系为||【即主树的某个结点为树时是子树的情况,返回true,逻辑关系||遇上true就可以直接停止寻找】
➡️做题思路:
用前序遍历遍历主树每一个结点,让每一个结点当作根节点去作树,与需要判断的子树判断两棵树是否相同
一旦找到,就返回true,停止寻找
✊动图示例:
👉代码实现:
bool isSameTree(struct TreeNode* p, struct TreeNode* q){//1.树都为NULL的时候 -- 相等//2.比较比到 NULL 的时候 == 前面都比完了,那就相等if (p == NULL && q == NULL){return true;}//判断p树和q树结构是否相同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) {//遍历root这棵树的每个结点,每个结点做子树根 ,去跟subRoot比较if (root == NULL){return false;}if (isSameTree(root, subRoot)){return true;}return isSubtree(root->left, subRoot)|| isSubtree(root->right, subRoot);}🏷️ 平衡二叉树【难度:简单】:mag:题目传送门:
Leetcode:110. 平衡二叉树给定一个二叉树,判断它是否是高度平衡的二叉树
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1
示例 1: 输入:root = [3,9,20,null,null,15,7]输出:true 示例 2: 输入:root = [1,2,2,3,3,null,null,4,4]输出:false 示例 3: 输入:root = []输出:true💡解题关键:
我们需要遍历树中的每一个结点,并让此结点作为根节点去看作一棵树,并比较此树的左右子树的高度是否平衡👉秒杀分析:
对于树中的每一个结点为根节点看作一棵树时,都需要时刻满足平衡条件,所以逻辑关系采用&&【即递归判断子树是否平衡时,只要一个不满足返回false,那整体就直接停止判断并返回false表示不平衡】
而遍历树中每一个结点时,我们采用前序遍历,这样一旦判断当前不满足平衡条件,就不需要判断后面的了
综上,秒杀口诀为:&&➕前序遍历
❗特别注意:
对于获取二叉树最大深度,我们采用的秒杀口诀为:后序遍历➕比较获取最大深度
在比较获取最大深度中,+1表示所获取子树的层数加上当前树的根节点的这一层
✊动图示例:
👉代码实现:
int maxDepth(struct TreeNode* root){if (root == NULL){return 0;}int leftDepth = maxDepth(root->left);int rightDepth = maxDepth(root->right);return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;}bool isBalanced(struct TreeNode* root) {if (root == NULL){return true;}int leftDepth = maxDepth(root->left);int rightDepth = maxDepth(root->right);return abs(leftDepth - rightDepth) < 2 && isBalanced(root->left) && isBalanced(root->right);}🏷️ 二叉树的构建及遍历(清华大学)【难度:较难】❗此题曾为清华大学OJ题,同学们一定要细心感受这一道题目哟❗
:mag:题目传送门:
牛客网:KY11. 二叉树的构建及遍历🌐