【牛客】二叉树遍历

约定不等于承诺〃 2024-03-23 13:04 104阅读 0赞

#### 目录 ####

*  题目
 *  解题过程
 *  解题代码

## 题目 ##

`题目链接`：[点击进入][Link 1]  
![在这里插入图片描述][65be80c4cd0f45eb9338c3f70ab78cf3.png]

## 解题过程 ##

对示例1中的样例即：`abc##de#g##f###`进行先序遍历建立一个二叉树，建立完成之后就是这样的，如下图：  
![在这里插入图片描述][f30018ddea984829880c86eed312cdc9.png]  
然后再将这颗树进行中序遍历进行最后的结果输出。  
无非就是用递归嘛  
整个题目的思路挺清晰的:**先先序遍历建立一棵二叉树，然后再对这棵二叉树进行中序遍历输出其值。**

## 解题代码 ##

#include<stdio.h>
    struct TreeNode
    {
        
        struct TreeNode* left;
        struct TreeNode* right;
        char val;
    };
    
    //先序建立二叉树
    struct TreeNode* CreateTree(char* a,int* pi)
    {
        
        if(a[*pi]=='#')
        {
        
            (*pi)++;
            return NULL;
        }
        struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        root->val=a[(*pi)++];
        root->left=CreateTree(a, pi);
        root->right=CreateTree(a, pi);
        return root;
    }
    
    //中序输出结果
    void InOrder(struct TreeNode* root)
    {
        
        if(root==NULL)
        {
        
            return;
        }
        InOrder(root->left);
        printf("%c ",root->val);
        InOrder(root->right);
    }
    
    int main()
    {
        
        char a[100];
        scanf("%s",a);
        int i=0;
        struct TreeNode* root=CreateTree(a,&i);
        InOrder(root);
        return 0;
    }

![在这里插入图片描述][9b43b45a335c422399d523936f2b87bc.png]

[Link 1]: https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking
[65be80c4cd0f45eb9338c3f70ab78cf3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/fb06263e8d5c402a9eecf7fa45842914.png
[f30018ddea984829880c86eed312cdc9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/792adf06f5e54849ac7e4d2d65851809.png
[9b43b45a335c422399d523936f2b87bc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/33cefbc394d24cdb8464901f4a66566e.png