360网站免费推广怎么做,建设网站需要的资金清单,网站专题活动策划方案,新邱建设网站写在前面学完上一篇文章的二叉树的遍历之后#xff0c;来尝试下面的习题吧开始做题144. 二叉树的前序遍历 - 力扣#xff08;LeetCode#xff09;94. 二叉树的中序遍历 - 力扣#xff08;LeetCode#xff09;145. 二叉树的后序遍历 - 力扣#xff08;LeetCode#xff09…写在前面学完上一篇文章的二叉树的遍历之后来尝试下面的习题吧开始做题144. 二叉树的前序遍历 - 力扣LeetCode94. 二叉树的中序遍历 - 力扣LeetCode145. 二叉树的后序遍历 - 力扣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(rootNULL) return;arr[(*returnSize)]root-val;PreOrder(root-left,arr,returnSize);PreOrder(root-right,arr,returnSize);
}int* preorderTraversal(struct TreeNode* root, int* returnSize)
{int *arrmalloc(sizeof(int)*2000); //定义数组用于存储遍历的返回值*returnSize0;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)
{*returnSize0; //数组大小设置为0if(rootNULL) //根结点为空没有遍历的必要直接返回空return NULL;struct TreeNode *queue[3000]; //定义一个队列int **arr(int**)malloc(sizeof(int*)*3000),front0,rear0;//定义一个二维数组*returnColumnSizes(int*)malloc(sizeof(int)*3000);//根结点入队queue[rear]root;while(front!rear)//这个是大循环{int temprear,k0;arr[*returnSize] (int*)malloc(sizeof(int) * (rear-front));while(fronttemp)//rear会变化{struct TreeNode *pqueue[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]中用于后续的访问。写在最后 点赞你的认可是我创作的动力⭐ 收藏你的青睐是我努力的方向✏️ 评论你的意见是我进步的财富
