【LeetCode&数据结构】二叉树的应用（二）——二叉树的前序遍历问题、二叉树的中序遍历问题、二叉树的后序遍历问题详解
🔥个人主页：艾莉丝努力练剑
❄专栏传送门：《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题
🍉学习方向：C/C++方向
⭐️人生格言：为天地立心，为生民立命，为往圣继绝学，为万世开太平
前言：牛客网和LeetCode的刷题都不可或缺，我们都要做一做，无论是参加竞赛还是笔试面试，至少能提升你的代码能力！洛谷的题目也可以去做一做。力扣的题目对提升代码能力很有帮助，需要有一点基础，几乎都是接口型的题目，关于接口型和IO型的区别我们在本专栏的第一篇【LeetCode】力扣题——轮转数组、消失的数字、数组串联中就介绍过了，这里不再赘述，我们进入今天的力扣题目介绍——
目录
正文
（一）思路
（二）解题过程
（三）完整代码
二、二叉树的中序遍历问题
（一）思路
（二）解题过程
（三）完整代码
三、二叉树的后序遍历问题
（一）思路
（二）解题过程
（三）完整代码
结尾
正文
一、二叉树的前序遍历问题
144. 二叉树的前序遍历
博主题解链接：先求总的二叉树结点个数，再前序遍历求解
题目描述：
题目示例和提示——
（一）思路
我们的思路是：先求总的二叉树结点个数，再前序遍历。
（二）解题过程
（三）完整代码
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; *//** * Note: The returned array must be malloced, assume caller calls free(). */ //求总的二叉树结点个数int BinarTreeSize(struct TreeNode* root){ if(root == NULL) { return 0; } return 1 + BinarTreeSize(root->left) + BinarTreeSize(root->right);}//前序遍历void preOrder(struct TreeNode* root,int* arr,int* pi){ if(root == NULL) { return; } arr[(*pi)++] = root->val; preOrder(root->left,arr,pi); preOrder(root->right,arr,pi);} //returnSize：表示要返回的数组的大小int* preorderTraversal(struct TreeNode* root, int* returnSize) { //二叉树结点个数 = *returnSize *returnSize = BinarTreeSize(root); int* arr = (int*)malloc(sizeof(int)*(*returnSize)); //前序遍历 int i = 0; preOrder(root,arr,&i); return arr;}
复杂度：时间复杂度：O(logn)，空间复杂度：O(n)。
二、二叉树的中序遍历问题
94. 二叉树的中序遍历
博主题解链接：先求总的二叉树结点个数，再中序遍历求解二叉树的中序遍历
题目描述：
题目示例和提示——
（一）思路
我们的思路是：先求总的二叉树结点个数，再中序遍历求解。
（二）解题过程
（三）完整代码
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; *//** * Note: The returned array must be malloced, assume caller calls free(). */// int* inorderTraversal(struct TreeNode* root, int* returnSize) { // } //求总的二叉树结点个数int BinarTreeSize(struct TreeNode* root){ if(root == NULL) { return 0; } return 1 + BinarTreeSize(root->left) + BinarTreeSize(root->right);}//中序遍历void inorder(struct TreeNode* root,int* arr,int* pi){ if(root == NULL) { return; } inorder(root->left,arr,pi); arr[(*pi)++] = root->val; inorder(root->right,arr,pi);} //returnSize：表示要返回的数组的大小int* inorderTraversal(struct TreeNode* root, int* returnSize) { //二叉树结点个数 = *returnSize *returnSize = BinarTreeSize(root); int* arr = (int*)malloc(sizeof(int)*(*returnSize)); //中序遍历 int i = 0; inorder(root,arr,&i); return arr;}
复杂度：时间复杂度：O(logn)，空间复杂度：O(n)。
三、二叉树的后序遍历问题
145. 二叉树的后序遍历
博主题解链接：先求总的二叉树结点个数，再后序遍历求解二叉树的后序遍历
题目描述：
题目示例和提示——
（一）思路
我们的思路是：先求总的二叉树结点个数，再前序遍历。
（二）解题过程
（三）完整代码
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; *//** * Note: The returned array must be malloced, assume caller calls free(). */ /** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; *//** * Note: The returned array must be malloced, assume caller calls free(). */ //求总的二叉树结点个数int BinarTreeSize(struct TreeNode* root){ if(root == NULL) { return 0; } return 1 + BinarTreeSize(root->left) + BinarTreeSize(root->right);}//后序遍历void postorder(struct TreeNode* root,int* arr,int* pi){ if(root == NULL) { return; } postorder(root->left,arr,pi); postorder(root->right,arr,pi); arr[(*pi)++] = root->val;} //returnSize：表示要返回的数组的大小int* postorderTraversal(struct TreeNode* root, int* returnSize) { //二叉树结点个数 = *returnSize *returnSize = BinarTreeSize(root); int* arr = (int*)malloc(sizeof(int)*(*returnSize)); //后序遍历 int i = 0; postorder(root,arr,&i); return arr;}
复杂度：时间复杂度：O(logn)，空间复杂度：O(1)。
结尾
往期回顾：
【LeetCode&数据结构】二叉树的应用（一）——单值二叉树问题、相同的树问题、对称二叉树问题、另一棵树的子树问题详解
由于本专栏的篇数越来越多，为了避免文章链接挂太多影响观感，博主之后的每一篇力扣刷题详解都只会附上前一篇的链接，最后一次完整链接是在之后会发布的【栈的应用——有效的括号问题详解】和【单链表的应用——环形链表问题详解】的文章结尾，本意是为了方便大家找到相应的详细的题解，现在文章多了，铸币博主没办法一一罗列，而且还会有“凑字数”的嫌疑，力扣刷题专栏的链接每次都会放在文章开头的位置，大家可自行前往！
感谢大家的理解与支持！
【LeetCode&数据结构】栈的应用——有效的括号问题详解
【LeetCode&数据结构】单链表的应用——环形链表问题详解
结语：本篇文章到这里就结束了，本文讲述的两道代码题并不适合C语言初学者，需要有一定的C语言基础，一定要学过数据结构与算法的算法复杂度、链表和二叉树的内容，才能写出复杂度较优的代码来。大家一定要自己动手敲一敲，不敲的话不仅容易忘记，也不方便将来复习。
