【数据结构】二叉树的四种遍历方式——必做题

写在前面

学完上一篇文章的二叉树的遍历之后，来尝试下面的习题吧

---

开始做题

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是什么意思？

1. returnSize是一个指向整数的指针，用于存储二维数组arr的行数，即层序遍历结果的大小。在函数执行完毕后，通过修改returnSize来告知调用者结果的大小。

2. returnColumnSizes是一个指向整数指针的指针，用于存储每一层中节点的数目。
   returnColumnSizes的指向的整数数组的大小应与arr的行数相同，即表示每一行中节点的数目。由于每一层的节点数目不同，因此我们需要动态分配一个整数数组来存储每一层中节点的数目。函数执行完毕后，returnColumnSizes指向的整数数组将包含每一层中节点的数目。

3. 需要注意的是，如果函数中没有任何一层节点，那么returnSize将为0，而returnColumnSizes指向的数组应为NULL。

• 问：为什么前者使用一级指针，后者使用二级指针？

1. 在这段代码中，returnSize使用一级指针，而returnColumnSizes使用二级指针，是因为它们所表示的信息不同。

2. returnSize指向的是整数类型的变量，用于表示层序遍历结果的行数，是一个单独的变量。因此，我们只需要通过一级指针将这个变量传递给函数，函数就可以修改这个变量的值，从而返回结果的行数。

3. returnColumnSizes指向的是整数类型的指针数组，用于表示每一行中节点的数目，是一个数组。由于这个数组的大小在函数调用时未知，因此我们需要使用二级指针将它传递给函数。在函数内部，我们需要先分配一个整数类型的数组，然后将这个数组的地址存储到returnColumnSizes所指向的地址中。因此，我们需要使用二级指针。

• int** arr=(int **)malloc(sizeof(int*)*3000);
  arr[*returnSize] = (int*)malloc(sizeof(int) * (rear-front));
  

1. 第一行代码定义了一个名为arr的指向指针的指针变量，分配了一个大小为sizeof(int*)3000字节的内存，该内存用于存储二维数组的每个一维数组的地址

2. 第二行代码则是为二维数组的一维数组分配内存，通过指针访问到第returnSize行，然后调用malloc函数分配一块大小为sizeof(int) * (rear-front)字节的内存，该内存用于存储一维数组中的元素，返回值为一维数组的首地址，使用强制类型转换将其转换为int类型，最后存储在arr[*returnSize]中，用于后续的访问。

---

写在最后

👍🏻 点赞，你的认可是我创作的动力！
⭐ 收藏，你的青睐是我努力的方向！
✏️ 评论，你的意见是我进步的财富！