【leetcode】二叉树的前序遍历➕中序遍历➕后序遍历

大家好，我是苏貝，本篇博客带大家刷题，如果你觉得我写的还不错的话，可以给我一个赞👍吗，感谢❤️

1. 二叉树的前序遍历

点击查看题目

在这里插入图片描述

根据提示，我们应该先动态开辟一个数组，之后按前序遍历的顺序将二叉树的值插入数组中，最后再返回这个数组。我们再来看函数给定的形参是什么：root是指向二叉树的根节点的指针，*returnsize是数组的大小，而非题目给我们已经开辟好的数组。
首先我们要想开辟数组，那么我们需要知道数组的大小，也就是二叉树的节点总数，用下面这个函数来返回节点总数

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

然后，我们将二叉树的值按前序遍历的顺序放入数组中。那数组的下标如何控制呢？一般可以用全局变量，但是要注意在每次调用下面这个函数时，将i置为0。否则进行第二次调用该函数时，数组的下标是从n（二叉树个数）开始的，而不是从0开始

int i=0;

void _preorderTraversal(struct TreeNode* root, int* arr)
{
    if(root==NULL)
        return;
    arr[i++]=root->val;
    _preorderTraversal(root->left,arr);
    _preorderTraversal(root->right,arr);
}

基于全局变量的不方便，我们也可以采用下面这种方法，即传一个初始化为0的变量的地址进来。

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);
}

好的，我们来看最终代码

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

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);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int n=TreeSize(root);
    *returnSize=n;
    int* arr=(int*)malloc(sizeof(int)*n);
    int i=0;
    _preorderTraversal(root,arr,&i);
    return arr;
}

2. 二叉树的中序遍历

点击查看题目
在这里插入图片描述

二叉树的中序遍历和下面的后序遍历思路同上，下面就只展示代码不做解释了

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

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);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int n=TreeSize(root);
    *returnSize=n;
    int* arr=(int*)malloc(sizeof(int)*n);
    int i=0;
    _inorderTraversal(root,arr,&i);
    return arr;
}

3. 二叉树的后序遍历

点击查看题目
在这里插入图片描述

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

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;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    int n=TreeSize(root);
    *returnSize=n;
    int* arr=(int*)malloc(sizeof(int)*n);
    int i=0;
    _postorderTraversal(root,arr,&i);
    return arr;
}