数据结构-构建二叉树

Question

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

提交格式：实现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}

Answer 1

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

#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 对二叉树进行先序遍历，将遍历结果存入数组中。