leetcode.com This is the practice of coding interviews for software developers. A total of more than 1,500 coding questions have been posted, and it seems that the same questions are often asked in actual interviews.
Introduction to golang + algorithm I will solve it with go and Python to strengthen the brain. (Python is weak but experienced)
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
(Japanese translation)
Given an array in which the elements are sorted in ascending order, convert it to a height-balanced BST.
In this problem, a height-balanced binary tree is defined as a binary tree in which the depths of the two subtrees of * all * nodes do not differ by more than one.
Example:
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/ \
-3 9
/ /
-10 5
Set the middle position as mid to make a balanced binary tree
mid is determined by left and right (Len (nums))
Once root is decided, create left and right there.
Answer code
class Solution(object):
def sortedArrayToBST(self, nums):
def convert(left, right):
if left > right:
return None
mid = (left + right) // 2
node = TreeNode(nums[mid])
node.left = convert(left, mid - 1)
node.right = convert(mid + 1, right)
return node
return convert(0, len(nums) - 1)
--I'll write it in Go too!
func sortedArrayToBST(nums []int) *TreeNode {
if len(nums) == 0 {
return nil
}
return &TreeNode{
Val: nums[len(nums)/2],
Left: sortedArrayToBST(nums[:len(nums)/2]),
Right: sortedArrayToBST(nums[len(nums)/2+1:]),
}
}
Recommended Posts