C - Tree UVA - 548

Love The Way You Lie 2022-03-22 06:06 120阅读 0赞

### 题目描述： ###

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

##### 题目链接：[https://uva.onlinejudge.org/index.php?option=com\_onlinejudge&Itemid=8&page=show\_problem&problem=489][https_uva.onlinejudge.org_index.php_option_com_onlinejudge_Itemid_8_page_show_problem_problem_489] #####

题意：给定一颗二叉树后序和中序，求出这颗二叉树从根节点到叶子点的和的最小值，输出最小值的叶子节点的值

##### 分析： #####

本题只要将二叉树的中序和后序遍历了解清楚，并找出他们之间的联系。那么本题的思路就有了。  
我们可以在草稿纸上画一个二叉树。  
![图片来源网络][3169607-e937e709b4160ff7.png]  
这颗二叉树的中序和后序遍历结果为：  
5 2 9 8 4 7 6  
5 9 2 4 6 7 8  
我们通过观察可以发现：  
根结点是后序遍历序列中最后一个数（即 8）。  
同时8在中序遍历中处于中间位置。通过观察，在中序遍历中，8的左边根结点（即结点8）的左子树，8的右边是结点8的右子树。

那么很显然，我们要做的是这样下面事情：  
1 找出后序遍历数组的最后一个元素。  
2 以后序遍历数组的最后一个元素为根据，将中序遍历数组分成左子树和右子树。  
3 以中序数组的左右子树为新子树，将后序数组分为左子树和右子树。  
4 将中序左子树，后序左子树作为一个新的，中序数组和后序数组，进行递归。同时将新根数的根赋值给先前根的左儿子。  
5 同理并同时处理右子树。  
很显然，这个过程可以通过递归来实现。

不过在实施过程中，依然遇到许多麻烦。在一开始，我的递归的实参是错的。导致wa了许久。然后，我在创建完树之后，寻找最小结点的时候错了。我一开始用层序遍历去寻找的。但是其实只要一个深搜就可以了，就像DP数字三角形那个题一样。  
我在改的过程中，加了许多的辅助语句。  
如下代码为AC代码：

#include"stdio.h"
    #include"string.h"
    #include"stdlib.h"
    //表一个结点
    typedef struct BiTreeNode
    {
        int value;
        int PreSum;
        struct BiTreeNode *LeftNode;
        struct BiTreeNode *RightNode;
    } BiTreeNode;
    //InOrderTraverse存中序遍历的结果。lenInOrder表有多少个数字。
    //Post存后序遍历的信息
    int InOrderTraverse[10001],lenInOrder;
    int PostOrderTraverse[10001],lenPostOrder;
    //将两个字符串转化为数字数组
    //这里有点繁琐，还可以优化成一半的长度
    void Change(char InOrder[],char PostOrder[])
    {
        int i,j,len,sum;
        len=strlen(InOrder);
        j=0;
        sum=0;
        for(i=0,j=0; i<len; i++)
        {
    
            if(InOrder[i]>='0'&&InOrder[i]<='9')
                sum=sum*10+(InOrder[i]-'0');
            else
            {
                InOrderTraverse[j++]=sum;
                sum=0;
            }
    
        }
        //这里是考虑到最后一个字符如果是空格，或者不为数字，就会造成差异，所以特判一下
        if(sum!=0)
        InOrderTraverse[j]=sum;
        else
            j--;
        lenInOrder=j;
        len=strlen(PostOrder);
        j=0;
        sum=0;
        for(i=0,j=0; i<len; i++)
        {
    
            if(PostOrder[i]>='0'&&PostOrder[i]<='9')
                sum=sum*10+(PostOrder[i]-'0');
            else
            {
                PostOrderTraverse[j++]=sum;
                sum=0;
            }
    
        }
        if(sum!=0)
        PostOrderTraverse[j]=sum;
        else
            j--;
        lenPostOrder=j;
    
    }
    BiTreeNode *Root;
    //正式创建二叉树
    /*/在分析过程中，我们提到要使用到中序和后序的遍历结果。
    我们会发现对于每一棵子树而言，他们的数据所对应的下标值是不一样的。
    所以在这里LeftInOrder表中序的最左边。其他同理。 
    void CreateBiTree(BiTreeNode **T,int LeftInOrder,int RightInOrder,int LeftPostOrder,int RightPostOrder)
    {
        int i,j,k,pos=-1;
        BiTreeNode *p,*s;
        //如果后序的左边大于右边了。直接return
        if(LeftPostOrder>RightPostOrder)
        {
            return ;
        }
        //利用这个循环在中序数组中找到根结点所对应的下标
        for(i=LeftInOrder; i<=RightInOrder; i++)
            if(InOrderTraverse[i]==PostOrderTraverse[RightPostOrder])
            {
                pos=i;
                break;
            }
            //pos==-1表没有找到，直接return
        if(pos==-1)
            return ;
           //申请空间
        *T=(BiTreeNode *)malloc(sizeof(BiTreeNode));
        (*T)->LeftNode=NULL;
        (*T)->RightNode=NULL;
        (*T)->PreSum=0;
      //这个空间的value值为这个子树根结点
        (*T)->value=InOrderTraverse[pos];
    //创建左右子树，注意这里的下标值，有讲究的
    //通过分析，得出以下规律。
        CreateBiTree(&((*T)->LeftNode),LeftInOrder,pos-1,LeftPostOrder,LeftPostOrder+pos-1-LeftInOrder);
        CreateBiTree(&((*T)->RightNode),pos+1,RightInOrder,LeftPostOrder+pos-LeftInOrder,RightPostOrder-1);
    }
    //这里是一个类似的数字三角形的dp，这里不再复述
    int ans,max;
    void dfs(BiTreeNode* root,int sum) {
    	sum += root->value;
    	if(root->LeftNode == NULL && root->RightNode == NULL) {
    		if(sum < max || (sum == max && root->value < ans)) {
    			ans = root->value;
    			max = sum;
    		}
    	}
    	if(root->LeftNode != NULL) {
    		dfs(root->LeftNode,sum);
    	}
    	if(root->RightNode != NULL) {
    		dfs(root->RightNode,sum);
    	}
    }
    int main()
    {
        char a[1000000];
        char b[1000000];
        int i,j,k;
        while(gets(a))
        {
            gets(b);
            Change(a,b);
        
           CreateBiTree(&Root,0,lenInOrder,0,lenPostOrder);
            max=99999;
            dfs(Root,0);
            printf("%d\n",ans);
          
        }
    }

以下是调式过程中的代码，可以利用其辅助信息更好的理解递归建造树  
同时注意这代码中LevelTraversal函数是错误的：

#include"stdio.h"
    #include"string.h"
    typedef struct BiTreeNode
    {
        int value;
        int PreSum;
        struct BiTreeNode *LeftNode;
        struct BiTreeNode *RightNode;
    } BiTreeNode;
    int InOrderTraverse[10001],lenInOrder;
    int PostOrderTraverse[10001],lenPostOrder;
    void Change(char InOrder[],char PostOrder[])
    {
        int i,j,len,sum;
        len=strlen(InOrder);
        j=0;
        sum=0;
        for(i=0,j=0; i<len; i++)
        {
    
            if(InOrder[i]>='0'&&InOrder[i]<='9')
                sum=sum*10+(InOrder[i]-'0');
            else
            {
                InOrderTraverse[j++]=sum;
                sum=0;
            }
    
        }
        InOrderTraverse[j]=sum;
        lenInOrder=j;
        len=strlen(PostOrder);
        j=0;
        sum=0;
        for(i=0,j=0; i<len; i++)
        {
    
            if(PostOrder[i]>='0'&&PostOrder[i]<='9')
                sum=sum*10+(PostOrder[i]-'0');
            else
            {
                PostOrderTraverse[j++]=sum;
                sum=0;
            }
    
        }
        PostOrderTraverse[j]=sum;
        lenPostOrder=j;
    
    }
    BiTreeNode *Root;
    void CreateBiTreeRoot()
    {
        Root=(BiTreeNode *)malloc(sizeof(BiTreeNode));
        Root->LeftNode=NULL;
        Root->RightNode=NULL;
        Root->PreSum=0;
    }
    void CreateBiTree(BiTreeNode **T,int LeftInOrder,int RightInOrder,int LeftPostOrder,int RightPostOrder)
    {
        int i,j,k,pos=-1;
        BiTreeNode *p,*s;
        if(LeftPostOrder>RightPostOrder)
        {
            return ;
        }
        for(i=LeftInOrder; i<=RightInOrder; i++)
            if(InOrderTraverse[i]==PostOrderTraverse[RightPostOrder])
            {
                pos=i;
                break;
            }
        if(pos==-1)
            return ;
        *T=(BiTreeNode *)malloc(sizeof(BiTreeNode));
        (*T)->LeftNode=NULL;
        (*T)->RightNode=NULL;
        (*T)->PreSum=0;
    
        (*T)->value=InOrderTraverse[pos];
        printf("（*T）->value=%d\n",(*T)->value);
        printf("LeftInOrder=%d pos=%d RightInOrder=%d\n",LeftInOrder,pos,RightInOrder);
        printf("LeftPostOrder=%d RightPostOrder=%d\n",LeftPostOrder,RightPostOrder);
        getchar();
        printf("即将进入左递归 \n");
        //if(LeftInOrder<=pos-1&&LeftPostOrder<=LeftPostOrder+pos-1-LeftInOrder)
        CreateBiTree(&((*T)->LeftNode),LeftInOrder,pos-1,LeftPostOrder,LeftPostOrder+pos-1-LeftInOrder);
        printf("即将进入右子树递归 \n");
        printf("LeftInOrder=%d pos=%d RightInOrder=%d\n",LeftInOrder,pos,RightInOrder);
        printf("LeftPostOrder=%d RightPostOrder=%d\n",LeftPostOrder,RightPostOrder);
        // if(pos+1<=RightInOrder&&LeftPostOrder+pos-LeftInOrder<=RightPostOrder-1)
        CreateBiTree(&((*T)->RightNode),pos+1,RightInOrder,LeftPostOrder+pos-LeftInOrder,RightPostOrder-1);
    }
    void LevelTraversal()
    {
        int i,j,k,min=999999,MIN;
        BiTreeNode *a[10002];
        Root->PreSum=Root->value;
        a[0]=Root;
        i=0;
        j=1;
        printf("即将进入层序遍历：\n");
        while(i<j)
        {
            a[i]->PreSum=a[i]->value+a[i]->PreSum;
            printf("即将进入if语句:\n");
            if(a[i]->LeftNode!=NULL)
            {
                a[j++]=a[i]->LeftNode;
    
            }
           if(a[i]->RightNode!=NULL)
            {
                a[j++]=a[i]->RightNode;
    
            }
         printf("判断左右子结点是否为空，进入判断:\n");
           if(a[i]->LeftNode==NULL&&a[i]->RightNode==NULL)
            {
    
                if(min>a[i]->PreSum)
                {
                    min=a[i]->PreSum;
                    MIN=a[i]->value;
                }
                if(min==a[i]->PreSum)
                {
                    if(MIN>a[i]->value)
                        MIN=a[i]->value;
                }
            }
        printf("第%d个结点以成功执行:\n",i);
            i++;
        }
        printf("%d\n",MIN);
    }
    int main()
    {
        char a[1000000];
        char b[1000000];
        int i,j,k;
        while(gets(a)!=NULL)
        {
            gets(b);
            Change(a,b);
            /*for(i=0;i<=lenInOrder;i++)
                printf("%d ",InOrderTraverse[i]);
            printf("\n");
            for(i=0;i<=lenPostOrder;i++)
                printf("%d ",PostOrderTraverse[i]);
            printf("\n");*/
            //  CreateBiTreeRoot();
    
            CreateBiTree(&Root,0,lenInOrder,0,lenPostOrder);
            printf("YESCreate\n");
            LevelTraversal();
        }
    }

[https_uva.onlinejudge.org_index.php_option_com_onlinejudge_Itemid_8_page_show_problem_problem_489]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=489
[3169607-e937e709b4160ff7.png]: /images/20220322/e9cc57da63534e99b921b0fd28b6592a.png