2013-11-23 23:53

题目描述：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并输出它的后序遍历序列。

输入：

输入可能包含多个测试样例，对于每个测试案例，

输入的第一行为一个整数n(1<=n<=1000)：代表二叉树的节点个数。

输入的第二行包括n个整数(其中每个元素a的范围为(1<=a<=1000))：代表二叉树的前序遍历序列。

输入的第三行包括n个整数(其中每个元素a的范围为(1<=a<=1000))：代表二叉树的中序遍历序列。

输出：

对应每个测试案例，输出一行：

如果题目中所给的前序和中序遍历序列能构成一棵二叉树，则输出n个整数，代表二叉树的后序遍历序列，每个元素后面都有空格。

如果题目中所给的前序和中序遍历序列不能构成一棵二叉树，则输出”No”。

 

样例输入：

81 2 4 7 3 5 6 84 7 2 1 5 3 8 681 2 4 7 3 5 6 84 1 2 7 5 3 8 6

样例输出：

7 4 2 5 8 6 3 1 No

题意分析： 　　给定一棵二叉树的前序遍历和中序遍历，计算出对应的后序遍历。如果给定的数据不是有效的遍历，则输出“No”。 　　　　前序遍历：根-左子树-右子树 　　　　中序遍历：左子树-根-右子树 　　　　后序遍历：左子树-右子树-根 　　因此，前序遍历的第一个节点为根节点，根据根节点的值在中序遍历中找到其对应位置，左边是左子树，右边是右子树，然后左右递归求解即可。 　　需要注意的是：输出后序遍历时，根节点最后输出，所以递归求解时，也应该在左右子树递归完成之后才处理根节点。 　　由于每次找出在中序遍历中找根节点的位置需要O(n)的查找时间，O(1)处理根节点，于是有T(n) = 2 * T(n / 2) + O(n) + O(1)，推导下复杂度： 　　　　T(n) = 2 * T(n / 2) + O(1) + O(n)　　　　T(n) = 2 * T(n / 2) + O(n) 　　　　T(n) = 4 * T(n / 4) + 2 * (O(n / 2)) + O(n) 　　　　T(n) = 4 * T(n / 4) + 2 * O(n) 　　　　T(n) = 2 ^ log(n) * T(1) + log(n) * O(n) 　　　　T(n) = O(n) + O(n * log(n)) 　　　　T(n) = O(n * log(n)) 　　递归求解，因为每个节点都会被递归到，所以空间复杂度为O(n)。

1 // 651379    zhuli19901106    1385    Accepted    点击此处查看所有case的执行结果    1024KB    1256B    0MS     2 // 201311142119 3 #include 
     
       4 #include 
      
        5 using namespace std; 6  7 void construct_tree(vector
       
         &a, vector
        
          &b, vector
         
           &c, int l1, int r1, int l2, int r2) 8 { 9     if(l1 > r1 || l2 > r2){10         return;11     }12     13     if(r1 - l1 != r2 - l2){14         return;15     }16     17     int mid;18     int nl, nr;19     20     for(mid = l2; mid <= r2; ++mid){21         if(b[mid] == a[l1]){22             nl = mid  - l2;23             nr = r2 - mid;24             if(nl > 0){25                 construct_tree(a, b, c, l1 + 1, l1 + nl, l2, mid - 1);26             }27             if(nr > 0){28                 construct_tree(a, b, c, r1 - nr + 1, r1, mid + 1, r2);29             }30             c.push_back(a[l1]);31             return;32         }33     }34     35 }36 37 int main()38 {39     vector
          
            a, b, c;40 int n;41 int tmp;42 int i;43 44 while(scanf("%d", &n) == 1){45 for(i = 0; i < n; ++i){46 scanf("%d", &tmp);47 a.push_back(tmp);48 }49 for(i = 0; i < n; ++i){50 scanf("%d", &tmp);51 b.push_back(tmp);52 }53 c.clear();54 construct_tree(a, b, c, 0, n - 1, 0, n - 1);55 a.clear();56 b.clear();57 if(c.size() < n){58 printf("No\n");59 }else{60 for(i = 0; i < n; ++i){61 printf("%d ", c[i]);62 }63 printf("\n");64 }65 c.clear();66 }67 68 return 0;69 }