【题目描述】
【思路解析】递归解决,从一个数组中找到最大元素所在位置作为根节点,再从其数组中其位置左边找最大元素做其左子节点,也是左子树的根节点,右边同理。构建这棵二叉树,最终返回构造二叉树的根节点。明显可以通过递归解决。
递归函数的主要作用是返回根节点,以及确定根节点的左右子节点。输入是在数组中,左右指针的数值。递归终止条件是当left=right,就返回空节点,说明当前节点的左或者右子节点为空。
C++:
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return dfs(nums,0,nums.size()) ;
}
TreeNode* dfs(vector<int>& nums,int left,int right){
if(left==right){
return NULL;
}
int max_index=Findmax(nums,left,right);
TreeNode* root=new TreeNode(nums[max_index]);
root->left=dfs(nums,left,max_index);
root->right=dfs(nums,max_index+1,right);
return root;
}
int Findmax(vector<int>& nums,int left,int right){
int max_index=0;
int max=-1000;
for(int i=left;i<right;i++){
if(nums[i]>max){
max_index=i;
max=nums[i];
}
}
return max_index;
}
};
python:
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
return self.dfs(nums,0,len(nums))
def dfs(self, nums: List[int],left,right)-> TreeNode:
if left==right:
return None
max_index=nums.index(max(nums[left:right]))
root=TreeNode(nums[max_index])
root.left=self.dfs(nums,left,max_index)
root.right=self.dfs(nums,max_index+1,right)
return root
时间复杂度为O(nlogn),每次递归函数中找最大值的过程时间复杂度为O(n),执行递归函数的次数与树的高度有关logn。空间复杂度主要来自于递归栈,O(logn).