【OJ】二叉树的遍历

zxctscl

发布于 2024-03-12 12:32:50

1380

文章被收录于专栏：zxctscl个人专栏zxctscl个人专栏

1. 144二叉树的前序遍历

1.1 分析

这里考察二叉树的前序遍历，遍历用递归就可以了，但是这里题目要求给的是遍历返回的是二叉树对应值前序遍历的结果，还要求按数组输出。 returnSize这里是用来记录节点的个数，不是数组。

那么就得考虑给这个数组开多大的空间？所以得先知道有多少个节点，先写一个Size函数来计算节点个数，如果是空节点就返回0，不然就先算左子树的节点数，再加上右子树的节点数，最后加上根节点1：

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

知道了节点的个数，那么就好为数组开空间：

 *returnSize=Size(root);
 int* arr=(int*)malloc(*returnSize*sizeof(int));

为了数组好利用下标访问，定义一个变量i。

为了方便，重新写一个函数来遍历：如果root为空，那么就结束递归。不为空，就在数组里面记录下root的val值，然后先对左子树进行递归，再对右子树进行递归。

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

最后在题目所给的函数基础上，调用Preorder1()，返回题目所要求的的数组就可以了：

Preorder1(root,arr,&i);
return arr;

1.2 代码

/**
 * 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 Size(struct TreeNode* root)
 {
    return root==NULL?0:Size(root->left)+Size(root->right)+1;
 }
 void Preorder1(struct TreeNode* root,int*arr,int* i)
 {
    if(root==NULL)
    {
        return;
    }
    arr[(*i)++]=root->val;   
    Preorder1(root->left,arr,i);
    Preorder1(root->right,arr,i);
 }

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

2. 94二叉树的中序遍历

2.1 分析

这题和上面前序遍历是一样的思路，就是把遍历节点的顺序该一下，其他都相同。也就将遍历的函数改为：先遍历左子树，然后数组来记录中间root的val值，再是右子树。

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

2.2 代码

/**
 * 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 Size(struct TreeNode* root)
{
    return root==NULL?0:Size(root->left)+Size(root->right)+1;
}
void Inorder(struct TreeNode* root,int* arr,int* i)
{
    if(root==NULL)
    {
        return;
    }
    Inorder(root->left,arr,i);
    arr[(*i)++]=root->val;
    Inorder(root->right,arr,i);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize=Size(root);
    int* arr=(int*)malloc(*returnSize*sizeof(int));
    int i=0;
    Inorder(root,arr,&i);
    return arr;
}

3. 145二叉树的后序遍历

3.1 分析

这题和上面前序遍历是一样的思路，就是把遍历节点的顺序该一下，其他都相同。也就将遍历的函数改为：先遍历左子树，再是右子树，最后数组来记录右边root的val值，

3.2 代码

/**
 * 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 Size(struct TreeNode* root)
{
    return root==NULL?0:Size(root->left)+Size(root->right)+1;
}
void postorder(struct TreeNode* root,int* arr,int* i)
{
    if(root==NULL)
    {
        return;
    }
    postorder(root->left,arr,i);
    postorder(root->right,arr,i);
    arr[(*i)++]=root->val;
}

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

有问题请指出，大家一起进步吧！！！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-03-11，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历