Leetcode654——最大二叉树

题目

【问题描述】

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

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

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

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

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

【输入形式】

     在一行中输入整数数组，用空格分隔开
【输出形式】

    输出生成的二叉树的树根节点的值。
【样例输入】

3 2 1 6 0 5

【样例输出】

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

【样例说明】

     测试数据的文件名为in.txt

【评分标准】

    该题目有10个测试用例，每通过一个测试用例，得10分。

设计

算法思路

1. 将文件中的数据读入数组中
2. 找到数组中最大数的下标maxIndex，以根据该index找到对应的value、将数组拆分为左右两个数组
3. 根据maxIndex对应的value构建根节点root
4. root的left为左数组的根节点，right为右数组的根节点
5. 深度优先的递归，当数组为空时返回
6. 把构建好的树以括号法展示出来

构建最大二叉树（recursive）

1. 使用vector接收数据
2. 设计findMaxIndex函数返回最大值下标
3. 在使用每个数组时，需要首、尾指针帮助确定数组范围
4. 左数组的首指针一定是start，尾指针是maxIndex - 1
5. 右数组的尾指针一定是end，首指针是maxIndex + 1
6. 如果start > end，证明这个子数组为空，则返回空指针

括号法展示（recursive)

1. 对于一个结点，如果其不为空，打印它的值
   1. 判断其有无孩子，若有孩子，先打印’(‘，再展示其左子树
   2. 判断其右子树是否为空，若不为空，则打印’,’，再展示其右子树
   3. 左右子树都展示完后，打印’)’
2. 如果结点为空，不操作

代码

#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
using namespace std;

struct BTNode
{
    int val;
    BTNode* left;
    BTNode* right;
    BTNode() : val(0), left(nullptr), right(nullptr) {}
    BTNode(int i) : val(i), left(nullptr), right(nullptr) {}  
};
  
int findMaxIndex(vector<int>& input, int start, int end){
    int maxIndex = start;
    for(int i = start; i <= end; i++){
        if(input[i] > input[maxIndex]){
            maxIndex = i;
        }
    }
    return maxIndex;
}

BTNode* createTree(vector<int>& input, int start, int end){
    if(start > end){
        return nullptr;
    }
    int maxIndex = findMaxIndex(input, start, end);
    BTNode* b = new BTNode(input[maxIndex]);
    b->left = createTree(input, start, maxIndex - 1);
    b->right = createTree(input, maxIndex + 1, end);
    return b;
}

void Display(BTNode* b){
    if(b != nullptr){
        cout << b->val;
        if(b->left != nullptr || b->right != nullptr){
            cout << '(';
            Display(b->left);
            if(b->right != nullptr){
                cout << ',';
            }
            Display(b->right);
            cout << ')';
        }
    }
}

int main(){
    ifstream file("in.txt");
    vector<int> input;
    int a;
    while(file >> a){
        input.push_back(a);
    }
    BTNode* root = createTree(input, 0, input.size() - 1);
    Display(root);
    return 0;
}