2 条题解

  • 0
    @ 2023-6-6 14:08:40

    首先根据观察我们可以发现前序遍历的第一个节点就是总的根节点,然后在中序遍历中找到总根节点的位置,由于中序遍历是左根右,因此中序遍历中最左边就是左子树的左边界,总根节点的左边就是左子树的右边界,总根节点的右边就是右子树的左边界,中序遍历的最右边就是右子树的右边界。依次类推,分为左右子树递归,求各自的次根节点。然后由于后序遍历是左右根,因此在每次递归完当前左右子树之后就输出根节点的值。

    • 0
      @ 2023-6-6 14:08:24
      #include<iostream>
      #include<algorithm>
      #include<string.h>
      using namespace std;
      char mid[100];
      char fir[100];
      int i,j;
      void dian(int fl,int fr,int ml,int mr)//前序遍历的左右边界,中序遍历的左右边界
      {
          int gen,llen,rlen;
          for(i=0;strlen(mid);i++)
            if(mid[i]==fir[fl])//找到根节点在中序遍历中的位置
            break;
            gen=i;
          llen=gen-ml;//记录左子树中节点的数量
          rlen=mr-gen;//记录右子树中节点的数量
          if(llen>0)
          {
              dian(fl+1,fl+llen,ml,ml+llen-1);//递归前序和中序的左子树
          }
          if(rlen>0)
          {
              dian(fr-rlen+1,fr,gen+1,gen+rlen);//递归前序和中序的右子树
          }
          cout<<fir[fl];//输出根节点
      }
      int main()
      {
          cin>>mid>>fir;
          dian(0,strlen(fir)-1,0,strlen(mid)-1);
          return 0;
      }
      
      • 1

      信息

      ID
      1391
      时间
      1000ms
      内存
      256MiB
      难度
      10
      标签
      递交数
      4
      已通过
      3
      上传者