m0_64279690 2022-12-29 14:19 采纳率: 33.3%
浏览 136
已结题

数据结构-构建二叉树

用先序序列和中序序列构建二叉树,采用二叉链表存储。编写递归算法,交换二叉树的左右子树,
输出新二叉树按先序遍历得到的结果。

提交格式:实现void solve(int n, int *preOrder, int *inOrder, int *outOrder)函数。
函数参数为序列长度n、先序序列preOrder、中序序列inOrder和输出序列outOrder。1<=n<=1000000,树的深度<=2000。
请不要printf输出任何内容。

输入样例1:
n=5,preOrder={1,2,3,4,5},inOrder={3,2,4,1,5}
输出样例1:
outOrder={1,5,2,4,3}

  • 写回答

8条回答 默认 最新

  • 极智视界 2022-12-30 10:34
    关注

    可以使用以下代码来实现递归交换二叉树左右子树的算法:

    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    
    // 通过先序遍历和中序遍历构建二叉树
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
      if (preorder.empty()) return NULL;
    
      int root_val = preorder[0];
      TreeNode* root = new TreeNode(root_val);
    
      int k = 0;
      // 找到根节点在中序遍历中的位置
      while (inorder[k] != root_val) ++k;
    
      vector<int> left_preorder(preorder.begin() + 1, preorder.begin() + 1 + k);
      vector<int> left_inorder(inorder.begin(), inorder.begin() + k);
      root->left = buildTree(left_preorder, left_inorder);
    
      vector<int> right_preorder(preorder.begin() + 1 + k, preorder.end());
      vector<int> right_inorder(inorder.begin() + k + 1, inorder.end());
      root->right = buildTree(right_preorder, right_inorder);
    
      return root;
    }
    
    // 递归交换二叉树的左右子树
    void swapSubtrees(TreeNode* root) {
      if (root == NULL) return;
      swap(root->left, root->right);
      swapSubtrees(root->left);
      swapSubtrees(root->right);
    }
    
    // 先序遍历二叉树,将遍历结果存入数组中
    void preOrderTraverse(TreeNode* root, vector<int>& outOrder) {
      if (root == NULL) return;
      outOrder.push_back(root->val);
      preOrderTraverse(root->left, outOrder);
      preOrderTraverse(root->right, outOrder);
    }
    
    void solve(int n, int* preOrder, int* inOrder, int* outOrder) {
      // 将先序遍历和中序遍历的数组转为 vector
      vector<int> preorder(preOrder, preOrder + n);
      vector<int> inorder(inOrder, inOrder + n);
    
      // 通过先序遍历和中序遍历构建二叉树
    TreeNode* root = buildTree(preorder, inorder);
    // 递归交换二叉树的左右子树
    swapSubtrees(root);
    // 先序遍历二叉树,将遍历结果存入数组中
    vector<int> outorder;
    preOrderTraverse(root, outorder);
    
    // 将 vector 转为数组
    copy(outorder.begin(), outorder.end(), outOrder);
    }
    

    在函数 solve 中,首先将先序遍历和中序遍历的数组转为 vector,然后调用函数 buildTree 来构建二叉树。然后调用函数 swapSubtrees 来递归交换二叉树的左右子树,最后调用函数 preOrderTraverse 对二叉树进行先序遍历,将遍历结果存入数组中。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(7条)

报告相同问题?

问题事件

  • 系统已结题 1月7日
  • 已采纳回答 12月30日
  • 创建了问题 12月29日

悬赏问题

  • ¥15 孟德尔随机化混杂因素
  • ¥15 关于react-hook组件用函数控制是否渲染的及时性问题。
  • ¥50 Linux下的软件,要做模块化拆分。进程间通信是否有开源框架可以借用?
  • ¥100 修改原有的MYSQL存储代码,在最右边添加多列数据
  • ¥20 Open Interpreter 使用时报错: still has pending operation at deallocation, the process may crash
  • ¥15 qt中链接动态链接库,调用其中的函数,该函数的参数需要传入回调函数,自己创建的回调函数无法作为参数传递进去
  • ¥15 matlab svm二分类代码问题
  • ¥40 求一款能支持ios15以上的屏蔽越狱插件。比较好用的
  • ¥15 C++ QT对比内存字符(形式不定)
  • ¥30 C++第三方库libiconv 远程安装协助