Skip to content

Latest commit

 

History

History
180 lines (133 loc) · 4.83 KB

108.convert-sorted-array-to-binary-search-tree.md

File metadata and controls

180 lines (133 loc) · 4.83 KB

题目地址(108. 将有序数组转换为二叉搜索树)

https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/

题目描述

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 给定有序数组: [-10,-3,0,5,9], 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树： 0 / \ -3 9 / / -10 5

前置知识

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节
  • airbnb

思路

由于输入是一个升序排列的有序数组。因此任意选择一点，将其作为根节点，其左部分左节点，其右部分右节点即可。 因此我们很容易写出递归代码。

而题目要求是高度平衡的二叉搜索树，因此我们必须要取中点。 不难证明：由于是中点，因此左右两部分差不会大于 1，也就是说其形成的左右子树节点数最多相差 1，因此左右子树高度差的绝对值不超过 1。

形象一点来看就像你提起一根绳子，从中点提的话才能使得两边绳子长度相差最小。

image.png

关键点

  • 找中点

代码

代码支持：JS，C++，Java，Python

JS Code:

varsortedArrayToBST=function(nums){// 由于数组是排序好的，因此一个思路就是将数组分成两半，一半是左子树，另一半是右子树// 然后运用“树的递归性质”递归完成操作即可。if(nums.length===0)returnnull;constmid=nums.length>>1;constroot=newTreeNode(nums[mid]);root.left=sortedArrayToBST(nums.slice(0,mid));root.right=sortedArrayToBST(nums.slice(mid+1));returnroot;};

Python Code:

classSolution: defsortedArrayToBST(self, nums: List[int]) ->TreeNode: ifnotnums: returnNonemid= (len(nums) -1) //2root=TreeNode(nums[mid]) root.left=self.sortedArrayToBST(nums[:mid]) root.right=self.sortedArrayToBST(nums[mid+1:]) returnroot

复杂度分析

  • 时间复杂度：$O(N)$
  • 空间复杂度：每次递归都 copy 了 N 的 空间，因此空间复杂度为 $O(N ^ 2)$

然而，实际上没必要开辟新的空间：

C++ Code:

classSolution { public: TreeNode* sortedArrayToBST(vector<int>& nums) { returnreBuild(nums, 0, nums.size()-1); } TreeNode* reBuild(vector<int>& nums, int left, int right) { // 终止条件：中序遍历为空if(left > right) { returnNULL; } // 建立当前子树的根节点int mid = (left+right)/2; TreeNode * root = newTreeNode(nums[mid]); // 左子树的下层递归 root->left = reBuild(nums, left, mid-1); // 右子树的下层递归 root->right = reBuild(nums, mid+1, right); // 返回根节点return root; } };

Java Code:

classSolution { publicTreeNodesortedArrayToBST(int[] nums) { returndfs(nums, 0, nums.length - 1); } privateTreeNodedfs(int[] nums, intlo, inthi) { if (lo > hi) { returnnull; } intmid = lo + (hi - lo) / 2; TreeNoderoot = newTreeNode(nums[mid]); root.left = dfs(nums, lo, mid - 1); root.right = dfs(nums, mid + 1, hi); returnroot; } }

Python Code:

classSolution(object): defsortedArrayToBST(self, nums): """ :type nums: List[int] :rtype: TreeNode """returnself.reBuild(nums, 0, len(nums)-1) defreBuild(self, nums, left, right): # 终止条件：ifleft>right: return# 建立当前子树的根节点mid= (left+right)//2root=TreeNode(nums[mid]) # 左右子树的下层递归root.left=self.reBuild(nums, left, mid-1) root.right=self.reBuild(nums, mid+1, right) returnroot

复杂度分析

  • 时间复杂度：$O(N)$
  • 空间复杂度：由于是平衡二叉树，因此隐式调用栈的开销为 $O(logN)$

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。

公众号【 力扣加加】知乎专栏【 Lucifer - 知乎】

点关注，不迷路！

close