题解 | #最小的K个数#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param input int整型一维数组 
# @param k int整型 
# @return int整型一维数组
#
class SortTree:
    def __init__(self,val:int):
        self.value = val
        self.left = None
        self.right= None
class Solution:
    def parseTree(self,root,k):
        print(root.value,k)
        rst=[]
        if root.left is not None:
            l,k = self.parseTree(root.left,k)
            rst += l
            if k == 0:
                return rst,k
        rst.append(root.value)
        k -= 1
        if k == 0:
            return rst,k
        if root.right is not None:
            l,k = self.parseTree(root.right,k)
            rst += l
            if k == 0:
                return rst,k
        return rst,k
        
    def add(self, root, node):
        if node > root.value:
            if root.right is not None:
                self.add(root.right,node)
            else:
                root.right = SortTree(node)
        else:
            if root.left is not None:
                self.add(root.left, node)
            else:
                root.left = SortTree(node)

    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        # write code here
        # 建二叉排序树，然后输出最小的4个数
        if len(input) == 0 or k == 0:
            return []
        r = root = SortTree(input[0])
        for i in range(1,len(input)):
            # 建树的过程也需要遍历
            root = r
            self.add(root,input[i])

        # 中序遍历树，计数：k
        rst,k=self.parseTree(r,k)
        return rst