[数据结构与算法]【LeetCode-654 | 最大二叉树】

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;


struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(): val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right): val(x), left(left), right(right) {}
};


class Solution {
public:
    /*
        注意如下：
            1.如果让空节点（空指针）进入递归，就不加if，如果不让空节点进入递归，就加if限制一下， 终止条件也会相应的调整。
            2.类似用数组构造二叉树的题目，每次分隔尽量不要定义新的数组，而是通过下表索引直接在原数组上操作，这样可以节约时间和空间上的开销。

        解题思路：利用前序遍历进行构造最大二叉树,根据构造规则，使用入参数组中最大值对应的数组下标划分入参数组。
    */
        // 1.确定递归函数入参及返回值
    TreeNode* Traversal(vector<int>& nums, int left, int right) {
        // 2.确定递归终止条件:当left >= right时，说明入参数组中已经没有剩余元素了，当前返回的节点为nullptr
        if(left >= right) return nullptr;

        // 3.确定单层递归逻辑
        int maxValueIndex = left;
        for(int i = left + 1; i < right; i++) {
            if(nums[i] > nums[maxValueIndex]) maxValueIndex = i;
        }

        TreeNode* root = new TreeNode(nums[maxValueIndex]);  // 入参数组中的最大值作为最大二叉树的根节点
        // 左闭右开：[left, maxValueIndex)
        root->left = Traversal(nums, left, maxValueIndex);
        // 左闭右开：[maxValueIndex + 1, right)
        root->right = Traversal(nums, maxValueIndex + 1, right);

        return root;
    }

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return Traversal(nums, 0, nums.size());
    }
};