Tree
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 63 1 2 5 6 7 47 8 11 3 5 16 12 188 3 11 7 16 18 12 5255255Sample Output 13255题目大意:
输入一个二叉树的中序和后序,输出一个叶子节点,该叶子节点到根的数值总和最小。
解题思路:
先通过后序和中序建立二叉树,在通过DFS进行搜索,找到符合题目要求的叶子。(需要使用全局变量来记录DFS过程中的最小和叶子)
中序和后序建立二叉树:
使用递归来逐步建立,由后序连确定当前递归中的分支的根节点,再在中序中找到根的位置,则中序中根左的为左子树的中序排列,根右的为右子树的中序。设此时左子树的长度为len,则当前的后序的前len个数据是左子树的后序排列。同理进行递归即可。右子树同理。
DFS:
设一个变量m,每次递归时作为实参进入调用,并执行m+=tree.data,则能保证递归到叶子节点时,m保存的是当前叶子到根节点的和,根据m的大小,即可选出符合题意的叶子节点。
Code:
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 struct tree 8 { 9 int data;10 int left;11 int right;12 } T[100100]; //数组模拟的二叉树13 int m_sum=100000000,pos; //用于DFS时保存结果14 int mid[100100],last[100100];15 int create_tree(int m1,int m2,int l1,int l2)16 {17 if (m1==m2)18 {19 T[m1].left=T[m1].right=-1;20 T[m1].data=mid[m1];21 return m1;22 }23 if (m1>m2)24 return -1;25 int i;26 for (i=0; i<=m2; i++)27 if (mid[i]==last[l2]) break;28 T[i].left=create_tree(m1,i-1,l1,l1+i-m1-1);//递归建树!!注意四个参数,runtime好多遍29 T[i].right=create_tree(i+1,m2,l1+i-m1,l2-1);30 T[i].data=mid[i];31 return i;32 }33 int min(int a,int b)34 {35 return a>b?b:a;36 }37 int dfs(int head,int m)38 {39 m+=T[head].data;40 if (T[head].left==-1&&T[head].right==-1)41 {42 if (m