0108. 将有序数组转换为二叉搜索树 · ttttt

# 0108. 将有序数组转换为二叉搜索树 ## 题目地址(108. 将有序数组转换为二叉搜索树) <https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/> ## 题目描述 ``` <pre class="calibre18">``` 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。示例: 给定有序数组: [-10,-3,0,5,9], 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树： 0 / \ -3 9 / / -10 5 ``` ``` ## 前置知识 - [二叉搜索树](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md) - [平衡二叉树](https://github.com/azl397985856/leetcode/blob/master/thinkings/basic-data-structure.md) - [递归](https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md) ## 公司 - 阿里 - 腾讯 - 百度 - 字节 - airbnb ## 思路由于输入是一个**升序排列的有序数组**。因此任意选择一点，将其作为根节点，其左部分左节点，其右部分右节点即可。因此我们很容易写出递归代码。而题目要求是**高度平衡**的二叉搜索树，因此我们必须要取中点。不难证明：`由于是中点，因此左右两部分差不会大于 1，也就是说其形成的左右子树节点数最多相差 1，因此左右子树高度差的绝对值不超过 1`。形象一点来看就像你提起一根绳子，从中点提的话才能使得两边绳子长度相差最小。 ![](https://img.kancloud.cn/2b/af/2bafd31e4bc6d0a864a5313ad3ac267b_847x643.jpg) ## 关键点 - 找中点 ## 代码代码支持：JS，C++，Java，Python JS Code: ``` <pre class="calibre18">``` var sortedArrayToBST = function (nums) { // 由于数组是排序好的，因此一个思路就是将数组分成两半，一半是左子树，另一半是右子树 // 然后运用“树的递归性质”递归完成操作即可。 if (nums.length === 0) return null; const mid = nums.length >> 1; const root = new TreeNode(nums[mid]); root.left = sortedArrayToBST(nums.slice(0, mid)); root.right = sortedArrayToBST(nums.slice(mid + 1)); return root; }; ``` ``` Python Code: ``` <pre class="calibre18">``` class Solution: def sortedArrayToBST(self, nums: List[int]) -> TreeNode: if not nums: return None mid = (len(nums) - 1) // 2 root = TreeNode(nums[mid]) root.left = self.sortedArrayToBST(nums[:mid]) root.right = self.sortedArrayToBST(nums[mid + 1:]) return root ``` ``` **复杂度分析** - 时间复杂度：O(N)O(N)O(N) - 空间复杂度：每次递归都 copy 了 N 的空间，因此空间复杂度为 O(N2)O(N ^ 2)O(N2) 然而，实际上没必要开辟新的空间： C++ Code: ``` <pre class="calibre18">``` class Solution { public: TreeNode* sortedArrayToBST(vector<int>& nums) { return reBuild(nums, 0, nums.size()-1); } TreeNode* reBuild(vector<int>& nums, int left, int right) { // 终止条件：中序遍历为空 if(left > right) { return NULL; } // 建立当前子树的根节点 int mid = (left+right)/2; TreeNode * root = new TreeNode(nums[mid]); // 左子树的下层递归 root->left = reBuild(nums, left, mid-1); // 右子树的下层递归 root->right = reBuild(nums, mid+1, right); // 返回根节点 return root; } }; ``` ``` Java Code: ``` <pre class="calibre18">``` class Solution { public TreeNode sortedArrayToBST(int[] nums) { return dfs(nums, 0, nums.length - 1); } private TreeNode dfs(int[] nums, int lo, int hi) { if (lo > hi) { return null; } int mid = lo + (hi - lo) / 2; TreeNode root = new TreeNode(nums[mid]); root.left = dfs(nums, lo, mid - 1); root.right = dfs(nums, mid + 1, hi); return root; } } ``` ``` Python Code: ``` <pre class="calibre18">``` class Solution(object): def sortedArrayToBST(self, nums): """ :type nums: List[int] :rtype: TreeNode """ return self.reBuild(nums, 0, len(nums)-1) def reBuild(self, nums, left, right): # 终止条件： if left > right: return # 建立当前子树的根节点 mid = (left + right)//2 root = TreeNode(nums[mid]) # 左右子树的下层递归 root.left = self.reBuild(nums, left, mid-1) root.right = self.reBuild(nums, mid+1, right) return root ``` ``` **复杂度分析** - 时间复杂度：O(N)O(N)O(N) - 空间复杂度：隐式调用栈的开销为 O(N)O(N)O(N) 更多题解可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。目前已经 37K star 啦。公众号【 [力扣加加](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)】知乎专栏【 [Lucifer - 知乎](https://www.zhihu.com/people/lu-xiao-13-70)】点关注，不迷路！