【Leetcode】KY11 二叉树遍历(牛客网）、144. 二叉树的前序遍历、94. 二叉树的中序遍历、145. 二叉树的后序遍历

系统管理员 2024-03-30 11:46 60阅读 0赞

>  作者：一个喜欢猫咪的的程序员
> 
> 专栏：《Leetcode》
> 
> 喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
> 
> ![19875ebe2e754183a07b326eee1fec37.jpeg][]
> 
> --------------------
> 
> **目录**
> 
> KY11 二叉树遍历 
> 
> 144. 二叉树的前序遍历
> 
> 94. 二叉树的中序遍历
> 
> 145. 二叉树的后序遍历
> 
> --------------------

## KY11 二叉树遍历 ##

[二叉树遍历\_牛客题霸\_牛客网 (nowcoder.com)![icon-default.png_t_M85B][]https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking][_nowcoder.com_icon-default.png_t_M85B_https_www.nowcoder.com_practice_4b91205483694f449f94c179883c1fef_tpId_60_tqId_29483_rp_1_ru_activity_oj_qru_ta_tsing-kaoyan_question-ranking]题目描述：

描述

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC\#\#DE\#G\#\#F\#\#\# 其中“\#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述：

输入包括1行字符串，长度不超过100。

输出描述：

可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。

--------------------

示例：

![60b4d0b18a3045b38580837cfd95d6e3.png][]

--------------------

思路：

**当str为\#时，返回NULL，i++，当str不为\#时，创建节点，并且设置值，left和right指向下一个str值递归下去。**

--------------------

代码实现：

#include <stdio.h>
    #include <stdlib.h>
    typedef struct BinaryTreeNode
    {
    	char data;
    	struct BinaryTreeNode* left;
    	struct BinaryTreeNode* right;
    }BTNode;
    BTNode*TreecCreate(char* str,int* i)
    {
        if(str[*i]=='#')
        {
            (*i)++;
            return NULL;
        }
        BTNode*root=(BTNode*)malloc(sizeof(BTNode));
        root->data=str[(*i)++];
        root->left=TreecCreate(str,i);
        root->right=TreecCreate(str,i);
        return root;
    }
    void InOrder(BTNode* root)
    {
        if (root == NULL)
        return;
    	InOrder(root->left);
    	printf("%c ", root->data);
    	InOrder(root->right);
    }
    int main() {
        int a, b;
        char str[100];
        scanf("%s",str);
        int i=0;
        BTNode*root=TreecCreate(str,&i);
        InOrder(root);
        return 0;
    }

--------------------

## 144. 二叉树的前序遍历 ##

![834f4b5a4ebf4a129820a0e92d2a06e8.png][]

int Treesize(struct TreeNode*root)
     {
         return root==NULL?0:Treesize(root->left)+Treesize(root->right)+1;
     }
     void PreOrder(int*a,struct TreeNode*root,int*i)
     {
         if (root == NULL)
    	{
    		return;
    	}
        a[(*i)++]=root->val;
    	PreOrder(a,root->left,i);
    	PreOrder(a,root->right,i);
     }
    int* preorderTraversal(struct TreeNode* root, int* returnSize){
        *returnSize=Treesize(root);
        int*a=(int*)malloc(*returnSize*sizeof(int));
        int i=0;
        PreOrder(a,root,&i);
        return a;
    }

## 94. 二叉树的中序遍历 ##

![2dc542b94df046479a3fc4a8bb2bdf0b.png][]

int Treesize(struct TreeNode*root)
     {
         return root==NULL?0:Treesize(root->left)+Treesize(root->right)+1;
     }
     void InOrder(int*a,struct TreeNode*root,int*i)
     {
         if (root == NULL)
    	{
    		return;
    	}
    	 InOrder(a,root->left,i);
        a[(*i)++]=root->val;
    	 InOrder(a,root->right,i);
     }
    int* inorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize=Treesize(root);
        int*a=(int*)malloc(*returnSize*sizeof(int));
        int i=0;
        InOrder(a,root,&i);
        return a;
    }

## 145. 二叉树的后序遍历 ##

![c44649d1658e44b6aa964672079bd036.png][]

int Treesize(struct TreeNode*root)
     {
         return root==NULL?0:Treesize(root->left)+Treesize(root->right)+1;
     }
     void PostOrder(int*a,struct TreeNode*root,int*i)
     {
         if (root == NULL)
    	{
    		return;
    	}
    	PostOrder(a,root->left,i);
    	PostOrder(a,root->right,i);
        a[(*i)++]=root->val;
     }
    int* postorderTraversal(struct TreeNode* root, int* returnSize){
    *returnSize=Treesize(root);
        int*a=(int*)malloc(*returnSize*sizeof(int));
        int i=0;
        PostOrder(a,root,&i);
        return a;
    }

[19875ebe2e754183a07b326eee1fec37.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9a4c612b10a64040a04a9a0f52f9def7.jpeg
[icon-default.png_t_M85B]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9fa76b5548c04a7da1a712427338a0ad.png
[_nowcoder.com_icon-default.png_t_M85B_https_www.nowcoder.com_practice_4b91205483694f449f94c179883c1fef_tpId_60_tqId_29483_rp_1_ru_activity_oj_qru_ta_tsing-kaoyan_question-ranking]: https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking
[60b4d0b18a3045b38580837cfd95d6e3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/def54404e0544b9ea5f42955e64689a8.png
[834f4b5a4ebf4a129820a0e92d2a06e8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8356154e597e4c3eb2553626b6551486.png
[2dc542b94df046479a3fc4a8bb2bdf0b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/287fdb76b5834dd589ee0c1dba8d4a50.png
[c44649d1658e44b6aa964672079bd036.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b9121f1f99744074a2344d7786104da6.png