二叉树的前中后序遍历＜难度系数⭐＞
【摘要】 1、二叉树的前序遍历＜难度系数⭐＞📝 题述：给你二叉树的根节点 root ，返回它节点值的前序遍历。💨 示例 1：输入：root = [1,null,2,3]输出：[1,2,3]💨 示例 2：输入：root = []输出：[]💨 示例 3：输入：root = [1]输出：[1]💨 示例 4：输入：root = [1,2]输出：[1,2]💨 示例 5：输入：root = [1,n...
1、二叉树的前序遍历＜难度系数⭐＞
📝 题述：给你二叉树的根节点 root ，返回它节点值的前序遍历。
💨 示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
💨 示例 2：
输入：root = []
输出：[]
💨 示例 3：
输入：root = [1]
输出：[1]
💨 示例 4：
输入：root = [1,2]
输出：[1,2]
💨 示例 5：
输入：root = [1,null,2]
输出：[1,2]
⚠ 注意：
1️⃣ 树中节点数目在范围 [0, 100] 内
2️⃣ -100 <= Node.val <= 100
🧷 平台：Visual studio 2017 && windows
🔑 核心思想：先实现 TreeSize 计算出二叉树的节点个数给 returnSize，并开辟好 returnSize 个 int 类型大小的数组。再调用子函数进行前序递归：如果每层函数栈帧中节点为空则结束栈帧，否则把节点放到数组里，并继续递归
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int BTDataType;
typedef struct TreeNode
{
int val;
struct TreeNode *left;
struct TreeNode *right;
}BTNode;
//malloc空间
BTNode* BuyNode(BTDataType x)
{
BTNode* node = malloc(sizeof(BTNode));
node->val = x;
node->left = NULL;
node->right = NULL;
return node;
}
//创建树
BTNode* CreatBinaryTree()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
node1->right = node2;
node2->left = node3;
return node1;
}
//求二叉树节点的个数
int TreeSize(struct TreeNode* root)
{
if (root == NULL)
{
return 0;
}
return TreeSize(root->left) + TreeSize(root->right) + 1;
}
//子函数用于递归 - 使用前序的方式
void _preorderTraversal(struct TreeNode* root, int* arr, int* pi)
{
if (root == NULL)
return;
//放节点
arr[(*pi)++] = root->val;
_preorderTraversal(root->left, arr, pi);
_preorderTraversal(root->right, arr, pi);
}
//Note: The returned array must be malloced, assume caller calls free().
//二叉树的前序遍厉
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
//*returnSize用于接收二叉树的节点个数
*returnSize = TreeSize(root);
//开辟*returnSize个int类型大小的空间
int* arr = (struct TreeSize*)malloc(sizeof(int)* *returnSize);
//因为preorderTraversal不适合递归，所以需要一个子函数；这里每一次递归都是一层函数栈帧，所以对于i来说想要保留正确的下标就要传地址
int i = 0;
_preorderTraversal(root, arr, &i);
return arr;
}
int main()
{
int returnSize = 0;
BTNode* root = CreatBinaryTree();
int* arr = preorderTraversal(root, &returnSize);
return 0;
}
2、二叉树中序遍历＜难度系数⭐＞
📝 题述：给定一个二叉树的根节点 root ，返回它的中序遍历。
💨 示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
💨 示例 2：
输入：root = []
输出：[]
💨 示例 3：
输入：root = [1]
输出：[1]
💨 示例 4：
输入：root = [1,2]
输出：[1,2]
💨 示例 5：
输入：root = [1,null,2]
输出：[1,2]
⚠ 注意：
1️⃣ 树中节点数目在范围 [0, 100] 内
2️⃣ -100 <= Node.val <= 100
🧷 平台：Visual studio 2017 && windows
🔑 核心思想：类似前序
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int BTDataType;
typedef struct TreeNode
{
int val;
struct TreeNode *left;
struct TreeNode *right;
}BTNode;
//malloc空间
BTNode* BuyNode(BTDataType x)
{
BTNode* node = malloc(sizeof(BTNode));
node->val = x;
node->left = NULL;
node->right = NULL;
return node;
}
//创建树
BTNode* CreatBinaryTree()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
node1->right = node2;
node2->left = node3;
return node1;
}
//求二叉树节点的个数
int TreeSize(struct TreeNode* root)
{
if (root == NULL)
{
return 0;
}
return TreeSize(root->left) + TreeSize(root->right) + 1;
}
//子函数用于递归 - 使用中序的方式
void _inorderTraversal(struct TreeNode* root, int* arr, int* pi)
{
if(root == NULL)
return;
_inorderTraversal(root->left, arr, pi);
arr[(*pi)++] = root->val;
_inorderTraversal(root->right, arr, pi);
}
//Note: The returned array must be malloced, assume caller calls free().
//二叉树的中序遍厉
int* inorderTraversal(struct TreeNode* root, int* returnSize){
//*returnSize接收二叉树的节点个数
*returnSize = TreeSize(root);
//开辟*returnSize个int类型大小的空间
int* arr = (struct TreeNode*)malloc(sizeof(int)* * returnSize);
//递归调用子函数
int i = 0;
_inorderTraversal(root, arr, &i);
return arr;
}
int main()
{
int returnSize = 0;
BTNode* root = CreatBinaryTree();
int* arr = inorderTraversal(root, &returnSize);
return 0;
}
3、二叉树的后序遍历＜难度系数⭐＞
📝 题述：给定一个二叉树，返回它的后序遍历。
💨 示例 ：
输入: [1,null,2,3]
输出: [3,2,1]
🧷 平台：Visual studio 2017 && windows
🔑 核心思想：类似前序
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int BTDataType;
typedef struct TreeNode
{
int val;
struct TreeNode *left;
struct TreeNode *right;
}BTNode;
//malloc空间
BTNode* BuyNode(BTDataType x)
{
BTNode* node = malloc(sizeof(BTNode));
node->val = x;
node->left = NULL;
node->right = NULL;
return node;
}
//创建树
BTNode* CreatBinaryTree()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
node1->right = node2;
node2->left = node3;
return node1;
}
//求二叉树节点的个数
int TreeSize(struct TreeNode* root)
{
if (root == NULL)
{
return 0;
}
return TreeSize(root->left) + TreeSize(root->right) + 1;
}
//子函数用于递归 - 使用后序的方式
void _postorderTraversal(struct TreeNode* root, int* arr, int* pi)
{
if (root == NULL)
return;
_postorderTraversal(root->left, arr, pi);
_postorderTraversal(root->right, arr, pi);
arr[(*pi)++] = root->val;
}
//Note: The returned array must be malloced, assume caller calls free().
//二叉树的后序遍历
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
//*returnSize接收二叉树的节点个数
*returnSize = TreeSize(root);
//开辟*returnSize个int类型大小的空间
int* arr = (struct TreeNode*)malloc(sizeof(int)* * returnSize);
//递归调用子函数
int i = 0;
_postorderTraversal(root, arr, &i);
return arr;
}
int main()
{
int returnSize = 0;
BTNode* root = CreatBinaryTree();
int* arr = postorderTraversal(root, &returnSize);
return 0;
}
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）