UVA548 Tree

Hits: 0

The meaning of the question
Enter the in-order and post-order traversal of a [binary tree] , please output a leaf node, the sum of the values ​​from the leaf node to the root is the smallest, and the leaf is the one with the smallest number. Input: Your program will read two lines from the input file (until the end of the file). The first line is the in-order traversal value sequence of the tree, and the second line is the post-order traversal value sequence of the tree. All values ​​will be different, greater than zero and less than or equal to 10000. Section 1<=N<=10000 of a binary tree. Output: For each tree description, you should output the value of the leaf node of the minimum path. In the presence of a multipath minimum, you should choose the path with the minimum value on the terminal leaf node, and output the terminal leaf with that minimum value.
enter

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

output

Idea: This question first builds a binary tree through the in-order and post-order, and then obtains the path length in the pre-order.
About three functions are needed: readline(int *arr): Read the in-order and post-order sequences.
createTree(int l1, int l2, int len): Build a binary tree
findmin(int v, int sum): Find the smallest path and smallest numbered node.

Reference Code

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;
int postorder[maxn],inorder[maxn],lch[maxn],rch[maxn],n,x;
int minsum,minv;
string str,str2;
    //getline(cin,str);
    if(!getline(cin,str)){
        return false;
    }
    stringstream s(str);
    n = 0 ,x;
     while (s>>x){ //stringstream can convert between strings and integers.
        arr[n++] = x;
    }
    return true;    
}
int  createTree ( int l1, int l2, int len) { //Create a binary tree in inorder and postorder. 
    if (len<= 0 ){ //The value of the left and right subtrees of the leaf node at the end of the recursion is 0 
        return  0 ;
    }
    int root = postorder[l2+len -1 ]; // 
    int len2= 0 ;
     while (inorder[l1+len2]!=root){ //Length of the left subtree of the root node of len2.
        len2++;
    }
    lch[root]=createTree(l1,l2,len2);
    rch[root] = createTree(l1+len2+ 1 ,l2+len2,len-len2 -1 );
     //rch[root] = createTree(l1+len2+1,l2+len2+1,len-len2-1) ;Because it is a post-order, the root node is at the end, so the processing of the right subtree should not +1 
    return root;
}

void  findmin ( int v, int sum) { //If there are multiple leaves with the smallest sum of weight paths, return the one with the smallest leaf node.
    sum += v;
    if (lch[v]== 0 &&rch[v]== 0 ){ //end of recursion 
        if (sum<minsum ||(sum == minsum &&v < minv )){ //exchange to satisfy the meaning of the question
            thin = I am;
            minv=v;

        } 
        return;
    }
    if(lch[v] > 0){
        findmin(lch[v],sum);
    } 
    if(rch[v]>0){
        findmin(rch[v],sum);
    }

} 
int main()
{
    while(readline(inorder)){
        readline(mailorder);
        //cout<<"hahah"<<endl;
        minsum=0xfffffff,minv=0xfffffff;
        createTree( 0 , 0 ,n); 
         //cout<<"Binary tree construction completed"<<endl; 
        findmin(postorder[n -1 ], 0 );
         cout <<minv<< endl ;
    }
    return 0;
}

You may also like...

Leave a Reply

Your email address will not be published.