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):
        # write your code here
        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):
        # write your code here
        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)

Here is a good answer:

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):
        # Write your code here
        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):
        # Write your code here.
        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)