力扣题---二叉树前、中、后序遍历

二叉树前序遍历

我们先来了解题目。

输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]

从示例不难看出，题目给定树的根结点，用前序遍历的方式，把二叉树的值放入数组中（若不知二叉树前、中、后序的顺序是什么，可以看这篇，里面有二叉树的详细解读

数据结构-二叉树-更新完整版    

那么题目要求得知，这里思路则是：

1.首先我们需要一个数组，数组大小多大

2.我们需要去计算树结点，来确定数组大小

3.然后通过前序遍历方式，放入数组中

4.最后返回数组。

int TreeSize(struct TreeNode* root)
{
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}

int* PerOrder(struct TreeNode* root,int* a,int* i)
{
    if(root==NULL)
    return;

    a[(*i)++]=root->val;//因为递归栈帧问题 i需要解引用

    PerOrder(root->left,a,i);
    PerOrder(root->right,a,i);

    return a;
}

int* preorderTraversal(struct TreeNode* root, int* returnSize){
 int size=TreeSize(root);//计算数组大小
 int* a=(int*)malloc(sizeof(int)*size);//创建数组
 int i=0;

 *returnSize=size;//返回相应的数组大小

 return PerOrder(root,a,&i);//前序遍历
}

既然前序完成，那么中、后序的问题则迎刃而解，我们只需要调换前序转为中、序即可

中序遍历

int TreeSize(struct TreeNode* root)
{
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}

int* InOrder(struct TreeNode* root,int* a,int* i)
{
    if(root==NULL)
    return;

    InOrder(root->left,a,i);
    a[(*i)++]=root->val;//因为递归栈帧问题 i需要解引用
    InOrder(root->right,a,i);

    return a;
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
int size=TreeSize(root);
int* a=(int*)malloc(sizeof(int)*size);
int i=0;
*returnSize=size;

return InOrder(root,a,&i);
}

后续遍历

 int TreeSize(struct TreeNode* root)
{
    return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;
}

int* CurOrder(struct TreeNode* root,int* a,int* i)
{
    if(root==NULL)
    return;

    CurOrder(root->left,a,i);
    CurOrder(root->right,a,i);
    a[(*i)++]=root->val;//因为递归栈帧问题 i需要解引用

    return a;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
int size=TreeSize(root);
int* a=(int*)malloc(sizeof(int)*size);
int i=0;
*returnSize=size;

return CurOrder(root,a,&i);
}

如果本篇对你有帮助，希望能获得您的赞！