UVA-548Tree(二叉树的递归遍历)

Tree

Time Limit: 3000MS   Memory Limit: Unknown   64bit IO Format: %lld & %llu

Submit Status

Description

You are to determine the value of the leaf node in a given binary tree that is the terminal node of a path of least value from the root of the binary tree to any leaf. The value of a path is the sum of values of nodes along that path.

Input

The input file will contain a description of the binary tree given as the inorder and postorder traversal sequences of that tree. Your program will read two line (until end of file) from the input file. The first line will contain the sequence of values associated with an inorder traversal of the tree and the second line will contain the sequence of values associated with a postorder traversal of the tree. All values will be different, greater than zero and less than 10000. You may assume that no binary tree will have more than 10000 nodes or less than 1 node.

Output

For each tree description you should output the value of the leaf node of a path of least value. In the case of multiple paths of least value you should pick the one with the least value on the terminal node.

Sample Input

3 2 1 4 5 7 6
3 1 2 5 6 7 4
7 8 11 3 5 16 12 18
8 3 11 7 16 18 12 5
255
255

Sample Output

1
3
255

题解:给出了一个二叉树的中序和后序遍历,让求树枝的最小总长的最小枝节点;思路是把这个二叉树求出来,然后找最小值,找最小值的地方错了好多次;必须要先找最小总长,再找相等的情况下最小枝节点;另外后序遍历其实倒过来就是先序遍历;在后序遍历的最后一个点其实就是根节点,根据这个在中序遍历里面递归找左右树;

代码:

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define SI(x) scanf("%d",&x)
#define mem(x,y) memset(x,y,sizeof(x))
#define PI(x) printf("%d",x)
#define P_ printf(" ")
const int INF=0x3f3f3f3f;
typedef long long LL;
const int MAXN=100010;
int v1[MAXN],v2[MAXN];
char s[MAXN];
int ans,minlength;
struct Node{
	int v;
	Node *L,*R;
	Node(){
		L=NULL;R=NULL;
	}
};
int init(char *s,int *v){
	int k=0;
	for(int i=0;s[i];i++){
		while(isdigit(s[i]))v[k]=v[k]*10+s[i++]-‘0‘;
		k++;
	}
//	for(int i=0;i<k;i++)printf("%d ",v[i]);puts("");
	return k;
}
int find(int n,int *v,int t){
	for(int i=n-1;i>=0;i--)
		if(v[i]==t)return i;
		 return 0;
}
Node* build(int n,int *v1,int *v2){
	Node *root;
	if(n<=0)return NULL;
	root=new Node;
	root->v=v2[n-1];
	int p=find(n,v1,v2[n-1]);
	root->L=build(p,v1,v2);
	root->R=build(n-p-1,v1+p+1,v2+p);
	return root;
}
void dfs(Node *root,int length){
	if(root==NULL)return;
	length+=root->v;
	if(root->L==NULL&&root->R==NULL){
		if(minlength>length)
        {
            minlength=length;
            ans=root->v;
        }
        else if(minlength==length)
        ans=min(ans,root->v);
		return;
	}
	dfs(root->L,length);
	dfs(root->R,length);
}
int main(){
	while(gets(s)){
		mem(v1,0);mem(v2,0);
		init(s,v1);
		gets(s);
		int k=init(s,v2);
		Node *root=build(k,v1,v2);
		ans=minlength=INF;
		dfs(root,0);
		printf("%d\n",ans);
	}
	return 0;
}

  

时间: 01-03

UVA-548Tree(二叉树的递归遍历)的相关文章

UVa 548 (二叉树的递归遍历) Tree

题意: 给出一棵由中序遍历和后序遍历确定的点带权的二叉树.然后找出一个根节点到叶子节点权值之和最小(如果相等选叶子节点权值最小的),输出最佳方案的叶子节点的权值. 二叉树有三种递归的遍历方式: 先序遍历,先父节点  然后左孩子  最后右孩子 中序遍历,先左孩子  然后父节点  最后父节点 后序遍历,先左孩子  然后右孩子  最后父节点 这里有更详细的解释: http://blog.csdn.net/sicofield/article/details/9066987 紫书上面写错了,后序遍历最后一

二叉树的递归遍历

#include<iostream> #include<stack> using namespace std; /*二叉树的前序遍历,按照 根节点->左孩子->右孩子 */ typedef struct node { char data; struct node *lchild,*rchild; }BinTree; void creatBinTree(BinTree * &root){ char ch; if(ch=getchar()){ if(ch=='#')

二叉树的递归遍历和非递归遍历(附详细例子)

mnesia在频繁操作数据的过程可能会报错:** WARNING ** Mnesia is overloaded: {dump_log, write_threshold},可以看出,mnesia应该是过载了.这个警告在mnesia dump操作会发生这个问题,表类型为disc_only_copies .disc_copies都可能会发生. 如何重现这个问题,例子的场景是多个进程同时在不断地mnesia:dirty_write/2 mnesia过载分析 1.抛出警告是在mnesia 增加dump

辛星算法教程第一节即二叉树的递归遍历

我们都知道,二叉树的递归遍历可以分为三种:前序遍历.中序遍历和后序遍历,其实这三种遍历方式大同小异,由于都是使用递归实现的,因此也比较简单. 首先是tree.h文件,代码如下: #ifndef TREE_H #define TREE_H #include <stdio.h> #include <malloc.h> #include <assert.h> typedef int ElemType; typedef struct Btree { ElemType val;

二叉树的递归遍历 The Falling Leaves UVa 699

题意:对于每一棵树,每一个结点都有它的水平位置,左子结点在根节点的水平位置-1,右子节点在根节点的位置+1,从左至右输出每个水平位置的节点之和 解题思路:由于上题所示的遍历方式如同二叉树的前序遍历,与天平那题不同,本题不需要构造出完整的结点左右子树,只需要构造出结点的相对位置,每次输入一个结点树,若为-1,则返回,否则依次递归执行input(p-1)与input(p+1). 代码如下: 1 #include<stdio.h> 2 #include<cstring> 3 #inclu

二叉树的递归遍历 Tree UVa548

题意:给一棵点带权的二叉树的中序和后序遍历,找一个叶子使得他到根的路径上的权值的和最小,如果多解,那该叶子本身的权值应该最小 解题思路:1.用getline()输入整行字符,然后用stringstream获得字符串中的数字 2.用数组in_oder[]和post_order[]分别表示中序遍历和后序遍历的顺序,用数组rch[]和lch[]分别表示结点的左子树和右子树 3.用递归的办法根据遍历的结果还原二叉树(后序遍历的最后一个树表示的是根节点,中序遍历的中间一个表示根节点) 4.二叉树构造完成后

2、二叉树:递归遍历

对二叉树而言,最为核心的操作就是遍历.遍历可以用递归的方式,也可以用循环的方式. 就递归遍历而言,又有“先序.中序.后续”三种不同的遍历顺序.通过下面的一个示意图可以从感官上来体会一下三种不同的遍历顺序: 为了学习二叉树的相关算法,首先需要构建一个二叉树的抽象类public abstract class BiTreeAbstract<T> ,该类中有一个表示结点的内部类Node,将结点的数据类型定义为泛型T以方便将其用于不同的数据类型. 1 package com.magicode.datas

【数据结构基础复习】二叉树的递归遍历(一)

一.绪论 今天来点简单的,好久没有写过代码了,基础知识都快忘了,从今天开始还是得简简单单的写一些,作为复习吧,不能光搞研究,代码给拉下了. 二.目的 复习二叉树的遍历 二叉树的遍历有三种,前中后.这里的前中后是根据树的根节点来看的,前序就是,根节点---左子节点---右子节点.其余类同.其实递归遍历没什么好谢的,都是教材上有的,这里直接把代码贴出来,不做过多的累述. //前序遍历: public void preOderRecur( Node root ){ if(root == null){

java 二叉树 深度优先递归遍历

深度优先遍历二叉树. 1. 中序遍历的递归算法: 若二叉树为空,则算法结束:否则: 中序遍历根结点的左子树: 访问根结点: 中序遍历根结点的右子树. 2. 前序遍历的递归算法: 若二叉树为空,则算法结束,否则: 访问根结点: 前序遍历根结点的左子树: 前序遍历根结点的右子树. 3. 后序遍历的递归算法: 若二叉树为空,则算法结束,否则: 后序遍历根结点的左子树: 后序遍历根结点的右子树: 访问根结点. package com.test6; /**  * 二叉树  *   * 描述: 1.二叉树的

二叉树的递归遍历和非递归遍历的实现

struct BinaryTreeNode{    int m_nValue;    BinaryTreeNode *m_pLeft;    BinaryTreeNode *m_pRight;}; //递归实现二叉树的遍历.递归算法比较简洁易懂这一就不做解释 void Preorder(BinaryTreeNode *pRoot){    if (pRoot == NULL)    {        return;    }    cout<<pRoot->m_nValue<<