LeetCode654 - 最大二叉树

题设

问题描述

给定一个不含重复元素的整数数组，一个以此数组构建的最大二叉树定义如下：

① 二叉树的根是数组中的最大元素。

② 左子树是通过数组中最大值左边部分构造出的最大二叉树。

③ 右子树是通过数组中最大值右边部分构造出的最大二叉树。

要求通过给定的数组构建最大二叉树，并且用括号表示法输出构建好的最大二叉树，假设给定的数组的大小在[1,1000]之间。

输入形式

在一行中输入整数数组，用空格分隔开

输出形式

输出生成的二叉树的树根节点的值。

样例输入

3 2 1 6 0 5

样例输出

6(3(,2(,1)),5(0))

题解

这题只需要递归输出就好。每次递归，找出最大的数，打印该数，添上括号、逗号，分别递归左右子树即可。注意当左子树存在但右子树为空时，左子树的根节点后不需要加逗号。

#include <iostream>
using namespace std;
const int N = 1010;

int a[N];

int get_max(int l, int r) {
  int res = l;
  while (l < r) {
    if (a[l] > a[res]) res = l;
    l++;
  }
  return res;
}

void create(int l, int r) {
  if (l >= r) return;
  if (l == r - 1) {
    printf("%d", a[l]);
    return;
  }
  int p = get_max(l, r);
  printf("%d(", a[p]);
  create(l, p);
  if (p + 1 < r) printf(",");
  create(p + 1, r);
  printf(")");
}

int main() {
  // freopen("in.txt", "r", stdin);
  int n = 0;
  while (cin >> a[n]) n++;
  create(0, n);
  puts("");
  return 0;
}