This is the 12th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Convert an ascending array to a balanced binary search tree

Problem description

108. Convert an ordered array to a binary search tree

Given an ascending sorted array, convert it to a balanced binary search tree (BST). Balanced binary search tree means that each node in the tree satisfies that the values of all nodes in the left subtree are less than the values of Node, and the values of all nodes in the right subtree are greater than the values of Node, and the difference between the number of nodes in the left and right subtrees is less than 1.

Example:

Input: nums = [-10,-3,0,5,9]

Output: [0, 3, 9, 10, null, 5]

To analyze problems

We all know that a middle order traversal of a binary search tree yields an ascending sequence. So the given array is the result of a middle-order traversal of a binary search tree. Let’s look at how to generate a highly balanced binary search tree from the middle order traversal of the tree.

Because the difference between the number of nodes in the left and right subtrees of a balanced binary search tree is no more than 1. So, we can choose the middle number of the array as the root node of the binary search tree. This ensures that the difference between the number of nodes on the left and right subtrees is no more than 1, making the tree balanced. If the given array length is odd, then the choice of the root node is the only, if the length of the array is an even number, you can choose the middle on the left side of the figure as a root node, or choose the middle to the right of the figure as a root node, select different Numbers were created as a root node balanced binary search trees are also different.

After the root node of the balanced binary search tree is determined, the rest of the numbers are located in the left and right subtrees of the balanced binary search tree. The left and right subtrees are also balanced binary search trees, so the balanced binary search tree can be created recursively.

There are three ways to construct a balanced binary search tree, depending on the root node chosen.

Methods a

If the left of the middle position is selected as the root node, the subscript of the root node is mid=(left+right) // 2.

class Solution: def sortedArrayToBST(self, nums): def cur(left, right): if left > right: Mid = (left + right) // 2 root = TreeNode(nums[mid]) root.left = cur(left, left) mid - 1) root.right = cur(mid + 1, right) return root return cur(0, len(nums) - 1)Copy the code

Method 2:

If the number on the right of the middle position is selected as the root node, the subscript of the root node is mid=(left+right+1) // 2.

class Solution: def sortedArrayToBST(self, nums): def cur(left, right): if left > right: Mid = (left + right + 1) // 2 root = TreeNode(nums[mid]) root.left = cur(left, left) mid - 1) root.right = cur(mid + 1, right) return root return cur(0, len(nums) - 1)Copy the code

Methods three

If any middle digit is selected as the root node, the subscript mid of the root node is randomly selected from (left+right)//2 and (Left +right+1)/2.

import random class Solution: def sortedArrayToBST(self, nums): def cur(left, right): if left > right: Random_data = random. Randint (0, 1) mid = (left + right + random_data) // 2 root = TreeNode(nums[mid]) # mid - 1) root.right = cur(mid + 1, right) return root return cur(0, len(nums) - 1)Copy the code