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

Problem (108. Convert an ordered array to a binary search tree)

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

Title description

Convert an ordered array arranged in ascending order into a highly balanced binary search tree. In this question, a highly balanced binary tree refers to a binary tree. The absolute value of the height difference between the left and right subtrees of each node does not exceed 1. example: Given an ordered array: [-10, -3,0,5,9], One possible answer is: [0,-3, 9,-10, null,5], which can represent the following highly balanced binary search tree： 0 / \ -3 9 / / -10 5 

Pre-knowledge

-Binary search tree -Balanced Binary tree -recursion

Company

-Ali -Tencent -Baidu -Byte

• airbnb

Idea

Since the input is an ordered array in ascending order of **. Therefore, choose any point and use it as the root node, the left part of the left node, and the right part of the right node. Therefore, it is easy for us to write recursive code.

The title requirement is a binary search tree with a high degree of balance, so we must take the midpoint. It is not difficult to prove: Since it is the midpoint, the difference between the left and right parts will not be greater than 1, that is to say, the number of nodes of the left and right subtrees formed by it will differ by at most 1, so the absolute value of the height difference between the left and right subtrees will not exceed 1.

From an image point of view, it's like you lift a rope, and if you lift it from it, you can minimize the difference in the length of the rope on both sides.

Key points

-Find the midpoint

Code

Code support: JS, C++, Java, Python

JS Code:

varsortedArrayToBST=function(nums){// Since the array is sorted, one idea is to divide the array into two halves, one half is the left subtree and the other half is the right subtree// Then use the “recursive nature of the tree” to complete the operation recursively.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

Complexity analysis

-Time complexity:$O(N)$ -Spatial complexity: Each recursion copies the space of N, so the spatial complexity is $O(N^2)$

However, there is actually no need to open up new space：

C++ Code:

classSolution { public: TreeNode* sortedArrayToBST(vector<int>& nums) { returnreBuild(nums, 0, nums. size()-1); } TreeNode* reBuild(vector<int>& nums, int left, int right) { // Termination condition: the middle-order traversal is emptyif(left > right) { returnNULL; } // Establish the root node of the current subtreeint mid = (left+right)/2; TreeNode * root = newTreeNode(nums[mid]); // Recursion of the lower layer of the left subtree root->left = reBuild(nums, left, mid-1); // Recursion of the lower layer of the right subtree root->right = reBuild(nums, mid+1, right); // Return to the root nodereturn 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): # Termination condition：ifleft>right: return# Establish the root node of the current subtreemid= (left+right)//2root=TreeNode(nums[mid]) # Recursion of the lower layer of the left and right subtreesroot. left=self. reBuild(nums, left, mid-1) root. right=self. reBuild(nums, mid+1, right) returnroot

Complexity analysis

-Time complexity:$O(N)$ -Spatial complexity: Since it is a balanced binary tree, the overhead of the implicit call stack is $O(logN)$

For more questions, please visit my LeetCode questions warehouse:https://github.com/azl397985856/leetcode . There are already 37K stars.

Public account 【Force Buckle plus】 Zhihu Column 【Lucifer-Zhihu】

Pay attention, don't get lost!