2 条题解

  • 0
    @ 2024-12-22 12:14:26

    递归求解的 注释过程,用于讲解:

    #include <bits/stdc++.h>
    using namespace std;
    string buildpostorder(string pres,string ins){
    	// 如果先序 或中序 有一个为空, 说明没有子树
    	
    	// 取得先序字符串的第一个字符- 根节点 
    	
    	//在中序字符串里面查找根节点的位置 
    	
    	//在中序字符串里面取得 中序的左子树 和右子树
    	string inleft=
    	string inright=
    	
    	 //计算左子树  的 长度  
    	 int leftlen=  ;
    	 
    	//从先序串中 截取 左右子树的  先序序列 
    	//跳过先序字符串的根节点  取leftlen长度
    	string preleft =   substr();
    	//截图右子树的先序串  inright在先序串中的 串
    	string preright =   
    	
    	//递归构造左子树的后续 和右子树的后续
    	string postleft =buildpostorder();
    	string posright =buildpostorder();
    	
    	return postleft+posright+根节点 ;
    }
    int main(){
        string prestring ,instring;
        cin>>  ; 
        string poststring = buildpostorder();  
        cout<<
    	return 0;
    }
    
    
    • 0
      @ 2024-12-10 16:36:24

      递归求解方法:

      #include <bits/stdc++.h>
      using namespace std;
      string buildPostOrder(const string &pre, const string &in) {
          // 如果先序或中序为空,说明没有子树
          if (pre.empty() || in.empty()) return "";
          // 根节点为先序遍历的第一个字符
          char root = pre[0];
          // 在中序序列中找到根节点的位置
          int rootPos = (int)in.find(root);
      
          // 中序遍历中,rootPos左侧为左子树中序,右侧为右子树中序
          string inLeft = in.substr(0, rootPos);
          string inRight = in.substr(rootPos + 1);
      
          // 左子树长度
          int leftLen = (int)inLeft.size();
      
          // 从先序中截取左、右子树的先序序列
          // 跳过根节点 pre[0],接下来 leftLen 个字符属于左子树先序
          string preLeft = pre.substr(1, leftLen);
          // 剩下的属于右子树先序
          string preRight = pre.substr(1 + leftLen);
      
          // 递归构造左子树的后序和右子树的后序
          string postLeft = buildPostOrder(preLeft, inLeft);
          string postRight = buildPostOrder(preRight, inRight);
      
          // 后序遍历 = 左子树后序 + 右子树后序 + 根节点
          return postLeft + postRight + root;
      }
      int main() {
          ios::sync_with_stdio(false);
          cin.tie(NULL);
          string preorder, inorder;
          cin >> preorder >> inorder;
          string postorder = buildPostOrder(preorder, inorder);
          cout << postorder << "\n";
      
          return 0;
      }
      
      • 1

      信息

      ID
      817
      时间
      1000ms
      内存
      256MiB
      难度
      5
      标签
      递交数
      26
      已通过
      14
      上传者