69-最大二叉树

自己的做法

算法思想

写一个递归函数：constructTree。

功能：将输入的数组转化成一个最大二叉树

参数：数组nums，左边界left，右边界right

返回值：该二叉树的根节点

递归终止条件：left > right。

递归函数具体实现：

找到该数组中最大元素，以该元素的值建立根节点，然后递归，传入该元素的左边数组和右边数组。

算法实现

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return constructTree(nums, 0, nums.size() - 1);
    }

    TreeNode * constructTree(vector<int>& nums, int left, int right) {
        if(left > right) {
            return nullptr;
        }
        int max_index = left;
        for(int i = left + 1; i <= right; i++) {
            if(nums[max_index] < nums[i]) {
                max_index = i;
            }
        }
        TreeNode * node = new TreeNode(nums[max_index]);
        node->left = constructTree(nums, left, max_index - 1);
        node->right = constructTree(nums, max_index + 1, right);
        return node;
    }
};

性能分析

时间复杂度：$O(n^2)$。一共被调用n次，每次找根节点时，都需要遍历当前索引范围内所有元素。总复杂度$O(nlogn)$。最坏情况是，nums有序，每次都要遍历到最后一个结点，总复杂度为$O(n^2)$。

空间复杂度：$O(n)$。平均情况，长度为n的数组递归调用深度为$O(logn)$。最坏情况为$O(n)$。