题目
给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
- 二叉树的根是数组 nums 中的最大元素。
- 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
- 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
返回有给定数组 nums 构建的 最大二叉树 。
示例 1：
输入：nums = [3,2,1,6,0,5] 输出：[6,3,5,null,2,0,null,null,1] 解释：递归调用如下所示： - [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。 - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。 - 空数组，无子节点。 - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。 - 空数组，无子节点。 - 只有一个元素，所以子节点是一个值为 1 的节点。 - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。 - 只有一个元素，所以子节点是一个值为 0 的节点。 - 空数组，无子节点。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
示例 2：
输入：nums = [3,2,1] 输出：[3,null,2,null,1]
解题
方法一：递归
和leetcode-106：从中序与后序遍历序列构造二叉树的思路一模一样.
通过数组构造二叉树，都可以尝试这种方式
python写法
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode: def build(in_left,in_right): if in_left>in_right: return None val = max(nums[in_left:in_right+1]) index = idx_map[val] root = TreeNode(val) root.right = build(index+1,in_right) root.left = build(in_left,index-1) return root idx_map = {val:idx for idx,val in enumerate(nums)} return build(0,len(nums)-1)
c++写法
class Solution { public: vector<int> nums; map<int,int> map; TreeNode* helper(int left,int right){ if(left>right) return nullptr; vector<int> tmp(nums.begin()+left,nums.begin()+right+1);//注意：切片的右边是取不到的。 int val=*max_element(tmp.begin(),tmp.end()); int mid=map[val]; TreeNode* root=new TreeNode(val); root->left=helper(left,mid-1); root->right=helper(mid+1,right); return root; } TreeNode* constructMaximumBinaryTree(vector<int>& nums) { this->nums=nums; for(int i=0;i<nums.size();i++){ map[nums[i]]=i; } return helper(0,nums.size()-1); } };
把vector用指针，效率更高
class Solution { public: vector<int>* nums; TreeNode* helper(int left,int right){ if(left>right) return nullptr; int mid = max_element(nums->begin()+left,nums->begin()+right+1)-nums->begin(); TreeNode* node=new TreeNode(nums->at(mid)); node->left=helper(left,mid-1); node->right=helper(mid+1,right); return node; } TreeNode* constructMaximumBinaryTree(vector<int>& nums) { this->nums=&nums; return helper(0,nums.size()-1); } };
java
class Solution { int nums[]; int getMaxIndex(int l,int r){ if(l>r) return -1; int val=nums[l]; int res=l; for(int i=l+1;i<=r;i++){ if(nums[i]>val){ val=nums[i]; res=i; } } return res; } TreeNode helper(int left,int right){ if(left>right) return null; int index=getMaxIndex(left,right); TreeNode node=new TreeNode(nums[index]); node.left=helper(left,index-1); node.right=helper(index+1,right); return node; } public TreeNode constructMaximumBinaryTree(int[] nums) { this.nums=nums; int n=nums.length; return helper(0,n-1); } }
