I tried LeetCode every day 108. Convert Sorted Array to Binary Search Tree (Python, Go)

What is Leetcode

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)

24th question (problem 108)

  1. Convert Sorted Array to Binary Search Tree the issue's details

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

Way of thinking

  1. Set the middle position as mid to make a balanced binary tree

  2. mid is determined by left and right (Len (nums))

  3. 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

I tried LeetCode every day 108. Convert Sorted Array to Binary Search Tree (Python, Go)
I tried LeetCode every day 110. Balanced Binary Tree (Python, Go)
I tried LeetCode every day 111. Minimum Depth of Binary Tree (Python, Go)
I tried LeetCode every day 13. Roman to Integer (Python, Go)
I tried LeetCode every day 167. Two Sum II --Input array is sorted (Python, Go)
I tried LeetCode every day 21. Merge Two Sorted Lists (Python, Go)
I tried LeetCode every day 7. Reverse Integer (Python, Go)
I tried LeetCode every day 112. Path Sum (Python, Go)
I tried LeetCode every day 20. Valid Parentheses (Python, Go)
I tried LeetCode every day 136. Single Number (Python, Go)
I tried LeetCode every day 118. Pascal's Triangle (Python, Go)
I tried LeetCode every day 125. Valid Palindrome (Python, Go)
I tried LeetCode every day 155. Min Stack (Python, Go)
I tried LeetCode every day 9. Palindrome Number (Python, Go)
I tried LeetCode every day 1. Two Sum (Python, Go)
I tried LeetCode every day 141. Linked List Cycle (Python, Go)
I tried LeetCode every day 14.Longest Common Prefix (Python, Go)
I tried LeetCode every day 119. Pascal's Triangle II (Python, Go)
I tried LeetCode every day 121 Best Time to Buy and Sell Stock (Python, Go)
I tried LeetCode every day 168. Excel Sheet Column Title (Python, Go)
I tried LeetCode every day 122. Best Time to Buy and Sell Stock II (Python, Go)
I tried LeetCode every day 160. Intersection of Two Linked Lists (Python, Go)
[Introduction] I tried to implement it by myself while explaining the binary search tree.
Python3 I don't know the balanced binary search tree, but I wish I had a sorted set.
I tried to convert a Python file to EXE (Recursion error supported)
I tried to touch Python (installation)
I tried Grumpy (Go running Python).
I tried to create a program to convert hexadecimal numbers to decimal numbers with python
Mayungo's Python Learning Episode 6: I tried to convert a character string to a number
I tried to solve AtCoder's depth-first search (DFS) in Python (result: TLE ...)
I tried to summarize Python exception handling
I tried to implement PLSA in Python
I tried to implement permutation in Python
I tried to implement PLSA in Python 2
Python3 standard input I tried to summarize
I tried to implement ADALINE in Python
I tried to implement PPO in Python
[Python] I tried to calculate TF-IDF steadily
I tried to touch Python (basic syntax)
I tried to make a castle search API with Elasticsearch + Sudachi + Go + echo
[LIVE] I tried to deliver the sunrise and sunset times nationwide every day
Convert FBX files to ASCII <-> BINARY in Python
I tried to get CloudWatch data with Python
I tried to output LLVM IR with Python
I tried to implement TOPIC MODEL in Python
I tried running faiss with python, Go, Rust
I tried to automate sushi making with python
I tried to implement selection sort in python
LeetCode I tried to summarize the simple ones
Python practice 100 knocks I tried to visualize the decision tree of Chapter 5 using graphviz
[Introduction] I tried to implement it by myself while explaining to understand the binary tree
[Python] I tried to summarize the array, dictionary generation method, loop method, list comprehension notation
I tried to graph the packages installed in Python
[Python] Convert decimal numbers to binary numbers, octal numbers, and hexadecimal numbers
When I tried to introduce python3 to atom, I got stuck
I tried to summarize how to use matplotlib of python
Convert NumPy array "ndarray" to lilt in Python [tolist ()]
I tried to implement Minesweeper on terminal with python
I tried to get started with blender python script_Part 01
I tried to touch the CSV file with Python
I tried to draw a route map with Python