二叉树的三序遍历
【摘要】 大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流作者简介:CSDN C/C++领域新星创作者https://blog.csdn.net/chuxinchangcun?type=blog掘金LV3用户 https://juejin.cn/us...
大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流
作者简介:
- CSDN C/C++领域新星创作者https://blog.csdn.net/chuxinchangcun?type=blog
- 掘金LV3用户 https://juejin.cn/user/1381426159953960
- 阿里云社区专家博主,星级博主,技术博主 https://developer.aliyun.com/profile/expert/5lkdbuggiiuhc
- 华为云云享专家 https://bbs.huaweicloud.com/community/myhomepage
题目
前序：144. 二叉树的前序遍历 - 力扣（LeetCode） (leetcode-cn.com)
/**
* 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().
*/
->要返回多个值放到数组中，数组是多大是不知道的，要把数组大小传回去
不用释放动态开辟的数组，调用者自己会释放
未知二叉树结点个数，如何开辟数组？
写法1：根据题目：树的结点最多100个
int* arr = (int*)malloc(sizeof(int));
但是这样可能造成较大的空间浪费
写法2：考虑顺序表扩容的写法
写法3：先统计二叉树的结点个数，再开辟空间
//统计结点个数
//左子树的结点+右子树的结点+1(根节点)
int TreeSize(struct TreeNode* root)
{
//空树->无结点返回0
return root == NULL ? 0:TreeSize(root->left) + TreeSize(root->right) +1;
}
前序：
注意事项1：
注意：不能把递归写到preorderTraversal函数里，不然每次递归进去都又开辟一个数组
所以：我们可以写一个子函数_preorderTraversal()
-
子函数需要的参数
- 根结点->用于递归
- 数组->用于存放结点的值
- 标识数组下标的变量地址！！！
错误写法
//统计结点个数
//左子树的结点+右子树的结点+1(根节点)
int TreeSize(struct TreeNode* root)
{
//空树->无结点返回0
return root == NULL ? 0:TreeSize(root->left) + TreeSize(root->right) +1;
}
//子函数 - 前序遍历存放数据
void _preorderTraversal((struct TreeNode* root,int* a,int i)
{
//空树：直接返回
if(root == NULL)
{
return ;
}
a[i++] = root->val;
_preorderTraversal(root->left,a,i);
_preorderTraversal(root->right,a,i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
int size = TreeSize(root);
int* a = (int*)malloc(sizeof(int)*size);
//开的空间较小，可以不用检查释放开辟失败
int i = 0;
//调用子函数存放二叉树的数据到数组中
_preorderTraversal(root,a,i);
*returnSize = size;//要返回数组的元素个数
return a;
}
注意事项2：
标识数组下标的变量要传地址！不然每次递归,不是对同一个i进行自增,
传地址过去 这样每次++都是对一个i 进行++
修正：传变量的地址
//统计结点个数
//左子树的结点+右子树的结点+1(根节点)
int TreeSize(struct TreeNode* root)
{
//空树->无结点返回0
return root == NULL ? 0:TreeSize(root->left) + TreeSize(root->right) +1;
}
//子函数 - 前序遍历存放数据
void _preorderTraversal(struct TreeNode* root,int* a,int* pi)
{
//空树：直接返回
if(root == NULL)
{
return ;
}
//类似前序遍历存放数据
//前序遍历：根 左子树 右子树
a[(*pi)++] = root->val;
_preorderTraversal(root->left,a,pi);
_preorderTraversal(root->right,a,pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
int size = TreeSize(root);
int* a = (int*)malloc(sizeof(int)*size);//不要忘了*结点个数
//开的空间较小，可以不用检查释放开辟失败
int i = 0;
//调用子函数存放二叉树的数据到数组中
_preorderTraversal(root,a,&i);
*returnSize = size;//要返回数组的元素个数
return a;
}
中序
和前序同理，只不过什么时候存放结点的位置发生改变 (类中序遍历)
//统计结点个数
//左子树的结点+右子树的结点+1(根节点)
int TreeSize(struct TreeNode* root)
{
//空树->无结点返回0
return root == NULL ? 0:TreeSize(root->left) + TreeSize(root->right) +1;
}
//子函数 - 后序遍历存放数据
void _inorderTraversal(struct TreeNode* root,int* a,int* pi)
{
//空树：直接返回
if(root == NULL)
{
return ;
}
//中序遍历：左子树 根 右子树
_inorderTraversal(root->left,a,pi);
a[(*pi)++] = root->val;
_inorderTraversal(root->right,a,pi);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
int size = TreeSize(root);
int* a = (int*)malloc(sizeof(int)*size);//不要忘了*结点个数
//开的空间较小，可以不用检查释放开辟失败
int i = 0;
//调用子函数存放二叉树的数据到数组中
_inorderTraversal(root,a,&i);
*returnSize = size;//要返回数组的元素个数
return a;
}
后序
和前序同理，只不过什么时候存放结点的位置发生改变 (类后序遍历)
//统计结点个数
//左子树的结点+右子树的结点+1(根节点)
int TreeSize(struct TreeNode* root)
{
//空树->无结点返回0
return root == NULL ? 0:TreeSize(root->left) + TreeSize(root->right) +1;
}
//子函数 - 后序遍历存放数据
void _postorderTraversal(struct TreeNode* root,int* a,int* pi)
{
//空树：直接返回
if(root == NULL)
{
return ;
}
//后序遍历：左子树 右子树 根
_postorderTraversal(root->left,a,pi);
_postorderTraversal(root->right,a,pi);
a[(*pi)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize)
{
int size = TreeSize(root);
int* a = (int*)malloc(sizeof(int)*size);//不要忘了*结点个数
//开的空间较小，可以不用检查释放开辟失败
int i = 0;
//调用子函数存放二叉树的数据到数组中
_postorderTraversal(root,a,&i);
*returnSize = size;//要返回数组的元素个数
return a;
}
使用容器vector的方法
前序:
class Solution {
public:
//注意传的是容器的引用
void _preorderTraversal(vector<int>& v,TreeNode* root)
{
if(root ==nullptr)
return;//空树就返回
v.push_back(root->val);//把值放到容器中
_preorderTraversal(v,root->left);//递归左树
_preorderTraversal(v,root->right);//递归右树
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> v;
if(root == nullptr)
{
return v;//返回空容器
}
_preorderTraversal(v,root);//调用递归函数
return v;//返回容器
}
};
中序
class Solution {
public:
//注意传的是容器的引用
void _inorderTraversal(vector<int>& v,TreeNode* root)
{
if(root == nullptr)
{
return ;//空树就返回
}
_inorderTraversal(v,root->left);//递归左树
v.push_back(root->val);//把值放到容器中
_inorderTraversal(v,root->right);//递归右树
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> v;
if(root == nullptr)
{
return v;//返回空容器
}
_inorderTraversal(v,root);
return v;
}
};
后序
class Solution {
public:
//注意传的是容器的引用
void _postorderTraversal(vector<int>& v,TreeNode* root)
{
if(root == nullptr)
{
return ;//空树就返回
}
_postorderTraversal(v,root->left);//递归左树
_postorderTraversal(v,root->right);//递归右树
v.push_back(root->val);//把值放到容器中
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> v;
if(root == nullptr)
{
return v;//返回空容器
}
_postorderTraversal(v,root);
return v;
}
};
\
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）