判断二叉搜索树

• 对于二叉搜索树，左子树的每一个点一定比根节点小，右子树每个点一定比根节点大。

• BST的 中序遍历一定有序 。

• 这道题给出了二叉搜索树的前序遍历，那么可以通过其前序遍历得到其中序遍历。因为BST的中序遍历一定有序。因此将其 sort 排序一遍即可得到其中序遍历的结果。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int preorder[N], inorder[N], postorder[N];
int cnt;

bool build(int il, int ir, int pl, int pr, int type)
{
  if (il > ir) return true;

  int root = preorder[pl];
  // 首先找到中序中的root的下标k
  int k = -1;
  if (type == 0)
  {
      for (int i = il; i <= ir; i ++ )
          if (inorder[i] == root)
          {
              k = i;
              break;
          }
      if (k == -1) return false;
  }
  else
  {
      for (int i = ir; i >= il; i -- )
          if (inorder[i] == root)
          {
              k = i;
              break;
          }
      if (k == -1) return false;
  }

  if (!build(il, k - 1, pl + 1, pl + 1 + (k - 1 - il), type)) return false;
  if (!build(k + 1, ir, pl + 1 + (k - 1 - il) + 1, pr, type)) return false;

  postorder[cnt ++ ] = root;

  return true;
}

int main()
{
  cin >> n;
  for (int i = 0; i < n; i ++ )
  {
      cin >> preorder[i];
      inorder[i] = preorder[i];
  }

  sort(inorder, inorder + n);

  if (build(0, n - 1, 0, n - 1, 0))
  {
      puts("YES");
      cout << postorder[0];
      for (int i = 1; i < n; i ++ ) cout << " " << postorder[i];
      puts("");
  }
  else
  {
      reverse(inorder, inorder + n);

      if (build(0, n - 1, 0, n - 1, 1))
      {
          puts("YES");
          cout << postorder[0];
          for (int i = 1; i < n; i ++ ) cout << " " << postorder[i];
          puts("");
      }
      else
          puts("NO");
  }

  return 0;
}