当前位置：首页 > news >正文

【数据结构与算法】二叉树基础OJ--下(巩固提高)

news 来源：原创 2024/5/13 16:19:23

前言：

上一篇文章我们讲到二叉树基础oj题目的练习，此篇文章是完成基础oj练习的完结篇。

传送-->【数据结构与算法】二叉树基础OJ -- 上 (巩固提高)-CSDN博客

💥🎈个人主页:Dream_Chaser～ 🎈💥

✨✨刷题专栏:http://t.csdn.cn/UlvTc

⛳⛳本篇内容:力扣与牛客网上二叉树OJ基础练习

KY11 二叉树遍历

题目描述:

解题思路:

leetcode 94.二叉树中序遍历(数组存储)

题目描述：

编辑

解题思路:

leetcode 145二叉树的后序遍历(数组存储)

题目描述：

解题思路：

KY11 二叉树遍历

题目来源:二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

题目描述:

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

输入描述:

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

输出描述:

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

示例1

输入:abc##de#g##f###
输出:c b e g d f a

解题思路:

先来复习一遍前序遍历，在此基础上，遍历一个比较难的字符串。

画出其前序遍历图：

画出其前序遍历递归图(省略一部分同理的)，剩下的可以根据上面的前序遍历图可求出

有了上面的基础，我们写出代码实现部分：

typedef int BTDataType;
typedef struct BTreeNode
{int val;struct BTreeNode* left;struct BTreeNode* right;
}BTNode;BTNode* BuyNode(BTDataType x)
{BTNode* root=(BTNode*)malloc(sizeof(BTNode));if(root == NULL){perror("malloc fail");return NULL;}root->val=x;root->left =NULL;root->right = NULL;return root;
}BTNode* CreateTree(char* a,int* pi)
{if(a[(*pi)] =='#'){(*pi)++;return NULL;}BTNode* root = BuyNode(a[(*pi)]);(*pi)++;root->left  = CreateTree(a, pi);root->right = CreateTree(a,pi);return root;
}
void InOrder(BTNode* 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;BTNode* root=CreateTree(a,&i);InOrder(root);printf("\n");
}

执行：

leetcode 94.二叉树中序遍历(数组存储)

题目来源:94. 二叉树的中序遍历 - 力扣（LeetCode）

题目描述：

给定一个二叉树的根节点 root ，返回 它的中序遍历 。

示例:

解题思路:

跟上一篇的前序遍历相差不大，就是将参数换个位置，其它不便说明。

代码实现：

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

代码执行：

leetcode 145二叉树的后序遍历(数组存储)

题目来源：145. 二叉树的后序遍历 - 力扣（LeetCode）

题目描述：

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例：

解题思路：

跟上一篇的前序遍历相差不大，就是将参数换个位置，其它不便说明。

代码实现：

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

此篇文章到此结束，感谢你的来访！