Tree UVA 548(DFS)

我就是我 2024-02-17 18:51 16阅读 0赞

解题思路：对于给定的二叉树的中序遍历和后序遍历，可以构造出这棵二叉树，方法是根据后序遍历找到树根。然后在中序遍历中找到树根，从而找出左右子树的结点列表，然后递归构造左右子树。

本题最不容易理解的就是构造树，当然需要耐下心来仔细理解

1.  \#include<iostream>
2.  \#include<string>
3.  \#include<sstream>
4.  using namespace std;
5.  const int maxn=10000+10;
6.  int in\_order\[maxn\],post\_order\[maxn\]; //中序序列和后序序列
7.  int lson\[maxn\],rson\[maxn\]; //左子树，右子树数组
8.  int n; 
9.  bool read(int \*t)\{ //读取数字序列
10.  string str;
11.  if(!getline(cin,str))return false;
12.  stringstream ss(str);
13.  n=0;
14.  int temp;
15.  while(ss>>temp)t\[n++\]=temp;
16.  return true;
17.  \}
18.  int buildtree(int l1,int r1,int l2,int r2)\{ //通过中、后序序列创建树 in\_order\[l1.......r1\], post\_order\[l2.........r2\];
19.  if(l1>r1)return 0; //当为树叶时，即无左右子树（lson\[root\]=0，rson\[root\]=0），返回0;
20.  int root=post\_order\[r2\];
21.  int temp=l1;
22.  while(in\_order\[temp\]!=root)temp++; //找到树根
23.  int lt=temp-l1; //左子树个数
24.  lson\[root\]=buildtree(l1,temp-1,l2,l2+lt-1);
25.  rson\[root\]=buildtree(temp+1,r1,l2+lt,r2-1);
26.  return root;
27.  \}
28.  int best,best\_sum; //当前树叶最优，当前权之和最优
29.  void dfs(int temp,int sum)\{ //dfs深度优先遍历
30.  sum+=temp;
31.  if(!lson\[temp\] && !rson\[temp\])\{ //树叶
32.  if(sum<best\_sum || sum==best\_sum&&temp<best )\{ 
33.  best\_sum=sum;
34.  best=temp;
35.  \}
36.  \}
37.  if(lson\[temp\])dfs(lson\[temp\],sum);
38.  if(rson\[temp\])dfs(rson\[temp\],sum);
39.  \}
40. int main()\{ 
41.  while(read(in\_order))\{ 
42.  read(post\_order);
43.  buildtree(0,n-1,0,n-1);
44.  best=best\_sum=1000000000;
45.  dfs(post\_order\[n-1\],0);
46.  cout<<best<<endl;
47.  \}
48.  return 0;
49. \}

本题最不容易理解的就是构造树，当然需要耐下心来仔细理解