写在前面
学完上一篇文章的二叉树的遍历之后,来尝试下面的习题吧
开始做题
144. 二叉树的前序遍历 - 力扣(LeetCode)
94. 二叉树的中序遍历 - 力扣(LeetCode)
145. 二叉树的后序遍历 - 力扣(LeetCode)
为什么将这三道题放在一起呢?因为只要你学会了前序遍历,那么中序和后序遍历就自然不在话下(修改递归顺序),我就不写三个解析水字数了😅,一箭三雕,举一反三的时刻到了😁
敬告:先去做完,再看解析。为方便判错,力扣上的题加了很多限制,有些变量必要难以理解
给你二叉树的根节点 root ,返回它节点值的 前序 遍历。
题目简简单单就一句话,正是上一篇文章所讲的代码,但是参数却有些让人看不懂,我们通常这样写
void preorderTraversal(struct TreeNode* root)
{if (root == NULL) return; // 如果节点为空,返回printf("%d ", root->val); // 先访问根节点preorderTraversal(root->left); // 再递归遍历左子树preorderTraversal(root->right); // 最后递归遍历右子树
但是力扣上的解析大都是这样的,为什么?
void PreOrder(struct TreeNode* root,int* arr,int* returnSize)
{if(root==NULL) return;arr[(*returnSize)++]=root->val;PreOrder(root->left,arr,returnSize);PreOrder(root->right,arr,returnSize);
}int* preorderTraversal(struct TreeNode* root, int* returnSize)
{int *arr=malloc(sizeof(int)*2000); //定义数组,用于存储遍历的返回值*returnSize=0;PreOrder(root,arr,returnSize);return arr;
}
原因:要求不同造成,需要更多参数;
首先这道题不像上一篇文章我们写的那样,直接打印出来结点数值,而力扣要求将结点数值存进一个数组,返回时还得返回整个数组,这样我们就得先定义一个数组arr ,又因为需要malloc,故需要将数组定义成指针的形式;
那returnSize的意思就是数组的长度,为什么要用指针呢?因为只有传值调用,指针接收,才能通过函数内returnSize的改变,进而影响returnSize被原本值,在这里初始值设为0就很巧妙,因为可以当成数组的下标;
至于前序遍历在这里就可以必须要时刻更新这三个参数,干脆就直接再封装成一个函数来进行递归调用。
中序遍历和后序遍历就很简单了,一箭三雕,举一反三的时刻到了😁
102. 二叉树的层序遍历 - 力扣(LeetCode)
给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
解析:这道题的难度有点大,耐心做
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*//*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*///用队列的顺序存储结构来实现,本身问题很简单,但上面的三条英文注释让整个题变得不简单起来
/*补充知识:二位动态整形数组的申请方法
int** arr=(int **)malloc(sizeof(int*)*3000);
arr[*returnSize] = (int*)malloc(sizeof(int) * (rear-front));
*/
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes)
{*returnSize=0; //数组大小设置为0if(root==NULL) //根结点为空,没有遍历的必要,直接返回空return NULL;struct TreeNode *queue[3000]; //定义一个队列int **arr=(int**)malloc(sizeof(int*)*3000),front=0,rear=0;//定义一个二维数组*returnColumnSizes=(int*)malloc(sizeof(int)*3000);//根结点入队queue[rear++]=root;while(front!=rear)//这个是大循环{int temp=rear,k=0;arr[*returnSize] = (int*)malloc(sizeof(int) * (rear-front));while(front<temp)//rear会变化{struct TreeNode *p=queue[front++];//出队arr[*returnSize][k++] = p->val;if(p->left) //如果左结点不空,左节点入队{queue[rear++]=p->left;}if(p->right) //如果右节点不空,右节点入队{queue[rear++]=p->right;}}(*returnColumnSizes)[*returnSize] = k;(*returnSize)++;}return arr;
}
问:这段代码中returnSize和returnColumnSizes是什么意思?
returnSize是一个指向整数的指针,用于存储二维数组arr的行数,即层序遍历结果的大小。在函数执行完毕后,通过修改returnSize来告知调用者结果的大小。
returnColumnSizes是一个指向整数指针的指针,用于存储每一层中节点的数目。
returnColumnSizes的指向的整数数组的大小应与arr的行数相同,即表示每一行中节点的数目。由于每一层的节点数目不同,因此我们需要动态分配一个整数数组来存储每一层中节点的数目。函数执行完毕后,returnColumnSizes指向的整数数组将包含每一层中节点的数目。
需要注意的是,如果函数中没有任何一层节点,那么returnSize将为0,而returnColumnSizes指向的数组应为NULL。
问:为什么前者使用一级指针,后者使用二级指针?
在这段代码中,returnSize使用一级指针,而returnColumnSizes使用二级指针,是因为它们所表示的信息不同。
returnSize指向的是整数类型的变量,用于表示层序遍历结果的行数,是一个单独的变量。因此,我们只需要通过一级指针将这个变量传递给函数,函数就可以修改这个变量的值,从而返回结果的行数。
returnColumnSizes指向的是整数类型的指针数组,用于表示每一行中节点的数目,是一个数组。由于这个数组的大小在函数调用时未知,因此我们需要使用二级指针将它传递给函数。在函数内部,我们需要先分配一个整数类型的数组,然后将这个数组的地址存储到returnColumnSizes所指向的地址中。因此,我们需要使用二级指针。
int** arr=(int **)malloc(sizeof(int*)*3000);
arr[*returnSize] = (int*)malloc(sizeof(int) * (rear-front));
第一行代码定义了一个名为arr的指向指针的指针变量,分配了一个大小为sizeof(int*)3000字节的内存,该内存用于存储二维数组的每个一维数组的地址
第二行代码则是为二维数组的一维数组分配内存,通过指针访问到第returnSize行,然后调用malloc函数分配一块大小为sizeof(int) * (rear-front)字节的内存,该内存用于存储一维数组中的元素,返回值为一维数组的首地址,使用强制类型转换将其转换为int类型,最后存储在arr[*returnSize]中,用于后续的访问。
写在最后
👍🏻 点赞,你的认可是我创作的动力!
⭐ 收藏,你的青睐是我努力的方向!
✏️ 评论,你的意见是我进步的财富!