# 177. Convert the sorted array into a binary search tree with the lowest height

Give a sort array (from small to large) and convert it into a binary search tree with the smallest height.

```class Solution:
"""
@param: A: an integer array
@return: A tree node
"""
def sortedArrayToBST(self, A):
if not A:
return
mid = len(A) // 2
node = TreeNode(A[mid])
node.left = self.sortedArrayToBST(A[:mid])
node.right = self.sortedArrayToBST(A[mid + 1:])
return node
```

# 900 · closest value in binary search tree

Give a non empty binary search tree and a target value to find the node value closest to the given value in BST

The more you write, the more you write. Finally, delete them and write them again.
In the exam, if you can't write complex, use the simplest way to achieve it, regardless of the time complexity.

```"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""

class Solution:
"""
@param root: the given BST
@param target: the given target
@return: the value in the BST that is closest to the target
"""

def closestValue(self, root, target):
self.li = []
self.dic = {}
self.BST(root, target)
return self.dic[min(self.li)]

def BST(self, root, target):
if not root:
return
diff = abs(target - root.val)
self.li.append(diff)
self.dic[diff] = root.val
if target > root.val:
self.BST(root.right, target)
else:
self.BST(root.left, target)
```

```def closestValue(self, root, target):
upper = root
lower = root
while root:
if target > root.val:
lower = root
root = root.right
elif target < root.val:
upper = root
root = root.left
else:
return root.val
if abs(upper.val - target) <= abs(lower.val - target):
return upper.val
return lower.val
```

# 1033 · minimum difference in BST

Given a binary search tree with definite root, it returns the minimum difference of the values of any two different nodes in the tree.

I wrote one, which can only pass part of the test. Not quite. But there are too many test examples for the test that I haven't passed, so I can't debug it.

```class Solution:
"""
@param root: the root
@return: the minimum difference between the values of any two different nodes in the tree
"""
def minDiffInBST(self, root):
self.min_val = float('inf')
self.dfs(root)
return self.min_val

def dfs(self, root):
if root.left is None and root.right is None:
return

if root.left:
left_diff = root.val - root.left.val
self.min_val = min(self.min_val, left_diff)
self.dfs(root.left)
if root.right:
right_diff = root.right.val - root.val
self.min_val = min(self.min_val, right_diff)
self.dfs(root.right)
```

The following is the answer. The answer is to traverse and find the minimum value. I made the mistake of yesterday and refused to solve it in the most violent way.

```import sys
class Solution(object):
def minDiffInBST(self, root):
"""
:type root: TreeNode
:rtype: int
"""
# Middle order traversal to find the minimum value of the difference.
nodes = []
queue= [root,]
while queue:
point = queue.pop(0)
nodes.append(point.val)
if point.left:
queue.append(point.left)
if point.right:
queue.append(point.right)
nodes.sort()
result = sys.maxint
for index,value in enumerate(nodes[1::]):
result = min(value - nodes[index],result)
return result
```

In programming, maxint /INT_MAX represents the maximum value that can be represented by an integer. In some cases, when programming, we may need to assign a value greater than any other integer value. Typically, people assign these values manually. For example, consider a list of integers that must use the for loop to find the minimum value.

# 1744. Incremental sequential search tree

Given a binary sort tree, traverse and rearrange the tree according to the middle order, so that the leftmost node in the tree is now the root of the tree, and each node has no left child node and only one right child node.

I learned the lesson from the previous question and used the simplest method, but after reading the answer, I still think I don't think much.

```class Solution:
"""
@param root: a binary search tree
@return: Root of a tree
"""
def increasingBST(self, root):
li = []
self.dfs(root, li)
root = self.create_tree(li)
return root

def create_tree(self, li):
node = TreeNode(li[0])
root = node
for i in li[1:]:
node.right = TreeNode(i)
node = node.right
return root

def dfs(self, root, li):
if not root:
return
self.dfs(root.left, li)
li.append(root.val)
self.dfs(root.right, li)
```

Answer: DFS inorder, I don't understand

```class Solution:
def increasingBST(self, root):
ans = self.cur = TreeNode(0)
self.inorder(root)
return ans.right
def inorder(self, root):
if root:
self.inorder(root.left)
root.left = None
self.cur.right = root
self.cur = root
self.inorder(root.right)
```

Keywords: Algorithm leetcode Interview

Added by Kunax on Sat, 12 Feb 2022 07:00:32 +0200