leetcode：654. 最大二叉树

题目

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

  1. 创建一个根节点，其值为 nums 中的最大值。
  2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
  3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

示例：

  1. 输入：s1 = "ab" s2 = "eidbaooo"
  2. 输出：true
  3. 解释：s2 包含 s1 的排列之一 ("ba").
  1. 输入：s1= "ab" s2 = "eidboaoo"
  2. 输出：false

解答 & 代码

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. private:
  14.     TreeNode* buildTree(vector<int> nums, int left, int right)
  15.     {
  16.         if(left > right)
  17.             return nullptr;
  19.         // 1. 找到最大值的下标，作为根节点
  20.         int rootIdx = left;
  21.         for(int i = left + 1; i <= right; ++i)
  22.         {
  23.             if(nums[i] > nums[rootIdx])
  24.                 rootIdx = i;
  25.         }
  26.         TreeNode* root = new TreeNode(nums[rootIdx]);
  27.         // 2. 递归构建左、右子树
  28.         root->left = buildTree(nums, left, rootIdx - 1);
  29.         root->right = buildTree(nums, rootIdx + 1, right);
  30.         return root;
  31.     }
  32. public:
  33.     TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
  34.         return buildTree(nums, 0, nums.size() - 1);
  35.     }
  36. };

复杂度分析：设二叉树节点数为 N（数组 nums 长为 N）

  • 时间复杂度[中等] 654. 最大二叉树 - 图1：会调用 N 次 buildTree() 函数来构建 N 个节点，每次都要遍历对应的子数组寻找最大值作为根节点
  • 空间复杂度 O(logN)：递归栈空间复杂度 = 递归深度 = 树深度

执行结果：

  1. 执行结果：通过
  3. 执行用时：148 ms, 在所有 C++ 提交中击败了 6.00% 的用户
  4. 内存消耗：370.9 MB, 在所有 C++ 提交中击败了 5.00% 的用户