HDU Binary Tree Traversals(二叉树重建+dfs)

青旅半醒 2024-02-17 19:05 82阅读 0赞

二叉树重建+DFS :中序遍历和先序遍历（或后序遍历）可以重建二叉树 ，和UVA 536一样的题

#include<cstdio>
    const int maxn=1000+10;
    int pre_order[maxn],in_order[maxn];
    int lch[maxn],rch[maxn];
    int flag;   //标识符号，用于输出格式的判断 
    int build_tree(int L1,int R1,int L2,int R2){
    	if(L1>R1)return 0;
    	int root=pre_order[L1];
    	int p=L2;
    	while(in_order[p]!=root)p++;
    	int cnt=p-L2; //左子树的个数 
    	lch[root]=build_tree(L1+1,L1+cnt,L2,p-1);
    	rch[root]=build_tree(L1+cnt+1,R1,p+1,R2);
    	return root;
    }
    void dfs(int cur){
    	if(!lch[cur] && !rch[cur]){ //如果是节点 
    		if(flag){printf("%d",cur);flag=0;}
    		else printf(" %d",cur);
    		return ;
    	}
    	if(lch[cur])dfs(lch[cur]);
    	if(rch[cur])dfs(rch[cur]);
    	if(flag)printf("%d",cur);
    		else printf(" %d",cur);
    }
    int main(){
    	int n;
    	while(scanf("%d",&n)==1){
    		for(int i=0;i<n;i++)scanf("%d",&pre_order[i]);
    		for(int i=0;i<n;i++)scanf("%d",&in_order[i]);
    		flag=1;
    		build_tree(0,n-1,0,n-1);
    		dfs(pre_order[0]);
    		printf("\n");
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，82人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU Binary Tree Traversals(二叉树重建+dfs)

二叉树重建+DFS :中序遍历和先序遍历（或后序遍历）可以重建二叉树，和UVA 536一样的题 include<cstdio> const int maxn

青旅半醒/ 2024年02月17日 19:05/ 0 赞/ 83 阅读

相关 UVA 536 Tree Recovery 二叉树重建（重建二叉树+DFS）

本题起初采用的是二叉树重建+dfs完成，然后看见网上不用建树也可以完成，也尝试了这种方法通过中序遍历和先序遍历（或后序遍历）可以重建二叉树，AC代码如下：二叉树重建+D

一时失言乱红尘/ 2024年02月17日 19:05/ 0 赞/ 104 阅读

相关数据结构-二叉树(binary tree)-二叉查找树(binary search tree)

\二叉树(binary) 二叉树就是节点的度不大于2的树，即树中每个节点的子节点最多只有两个。每个节点的子节点分为左子节点和右子节点，并且左右子节点的顺序不能改变。 ![

朱雀/ 2022年08月22日 01:24/ 0 赞/ 83 阅读

相关 Binary Tree Traversals hdu 1710 c++

Binary Tree Traversals Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 327

水深无声/ 2022年08月10日 13:50/ 0 赞/ 76 阅读

相关 Leetcode: Binary Tree Inorder Traversal（二叉树中序遍历）

题目： Given a binary tree, return the inorder traversal of its nodes’ values. For examp

蔚落/ 2022年08月07日 11:40/ 0 赞/ 177 阅读

相关 Leetcode: Binary Tree Preorder Traversal（二叉树前序遍历）

题目： Given a binary tree, return the preorder traversal of its nodes’ values. For exam

忘是亡心i/ 2022年08月07日 10:55/ 0 赞/ 58 阅读

相关 102. Binary Tree Level Order Traversal （二叉树层次遍历）

Given a binary tree, return the level order traversal of its nodes' values. (ie, from le

野性酷女/ 2022年07月15日 01:17/ 0 赞/ 155 阅读

相关 94. Binary Tree Inorder Traversal（中序遍历二叉树）

Given a binary tree, return the inorder traversal of its nodes' values. For example:

迷南。/ 2022年07月14日 06:07/ 0 赞/ 184 阅读

相关 leetcode 145. Binary Tree Postorder Traversal 二叉树后续遍历

Given a binary tree, return the postorder traversal of its nodes’ values. For example:

快来打我*/ 2022年06月08日 06:24/ 0 赞/ 205 阅读

相关 M - Binary Tree Traversals（建立二叉树）

题目描述： A binary tree is a finite set of vertices that is either empty or consists of a

末蓝、/ 2022年03月20日 08:10/ 0 赞/ 207 阅读