每日一道算法题--leetcode 654--最大二叉树--python&C++

400 阅读1分钟

【题目描述】

【思路解析】

递归解决,从一个数组中找到最大元素所在位置作为根节点,再从其数组中其位置左边找最大元素做其左子节点,也是左子树的根节点,右边同理。构建这棵二叉树,最终返回构造二叉树的根节点。明显可以通过递归解决。

递归函数的主要作用是返回根节点,以及确定根节点的左右子节点。输入是在数组中,左右指针的数值。递归终止条件是当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).