leetcode/utils.py

import pytest

# 链表
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 数组转链表
def arr_to_linklist(arr):

    p = None
    for n in reversed(arr):
        node = ListNode(n)
        node.next = p
        p = node
    return p

# 链表转数组
def linkList_to_arr(head):
    res = []
    cur = head
    while cur is not None:
        res.append(cur.val)
        cur = cur.next

    return res

# 数组转链表
def list_to_linklist(arr):
    head = ListNode(arr[0])
    p = head
    for i in range(1, len(arr)):
        p.next = ListNode(arr[i])
        p = p.next
    return head

# 树
# class Bnode(object):
#     def __init__(self, data, left=None, right=None):
#         self.data = data
#         self.left = left
#         self.right = right
#
# class Btree(object):
#     def __init__(self, root=None):
#         self.root = root
#
#     @classmethod
#     def bulid(cls, list):
#         node_dict = {}
#         # 制作节点
#         for item in list:
#             data = item['data']
#             node_dict[data] = Bnode(data)
#         # 把节点组装成数
#         for item in list:
#             data = item['data']
#             node = node_dict[data]
#             if node['is_root']:
#                 root = node
#             node.left = node_dict.get(item['left'])
#             node.right = node_dict.get(item['right'])
#         return cls(root)
#
#     def preorder(self, subtree):
#         # 先序
#         if subtree is not None:
#             print(subtree.data)
#             self.preorder(subtree.left)
#             self.preorder(subtree.right)
#
#     def reverse(self, subtree):
#         # 后序
#         if subtree is not None:
#             subtree.left, subtree.right = subtree.right, subtree.left
#             self.reverse(self, subtree.left)
#             self.reverse(self, subtree.right)

#定义二叉树结点类型
class BiTNode:
  def __init__(self,root):
    self.root = root
    self.left_child = None
    self.right_child = None

#前序遍历
def print_tree_pre_order(root):
    # 先判断二叉树是否为空
    if root is None:
        return root
    # 先根
    print(root.data)
    # 再左
    if root.left_child is not None:
        print_tree_pre_order(root.left_child)
    # 再右
    if root.right_child is not None:
        print_tree_pre_order(root.right_child)

#中序遍历二叉树
def print_tree_mid_order(root):
    # 先判断二叉树是否为空,当左右节点都为空时
    if root is None:
        return
    # 中序遍历 左根右
    # 遍历左子树
    if root.left_child is not None:
        print_tree_mid_order(root.left_child)
    # 遍历根节点
    print(root.data)
    # 遍历右子树
    if root.right_child is not None:
        print_tree_mid_order(root.right_child)

#后序遍历
def print_tree_after_order(root):
    # 先判断二叉树是否为空
    if root is None:
        return root
    # 再左
    if root.left_child is not None:
        print_tree_after_order(root.left_child)
    # 再右
    if root.right_child is not None:
        print_tree_after_order(root.right_child)
    # 先根
    print(root.data)

def array_to_bitree(array):
    # 判断arr是否为空
    if len(array) == 0:
        return BiTNode(array[0])
    mid = len(array) // 2  # 有序数组的中间元素的下标
    if len(array) > 0:
        # 将中间元素作为二叉树的根
        root = BiTNode(array[mid])
        # 如果左边的元素个数不为零，则递归调用函数，生成左子树
        if len(array[:mid]) > 0:
            root.left_child = array_to_bitree(array[:mid])
        # 如果右边的元素个数不为零，则递归调用函数，生成左子树
        if len(array[mid + 1:]) > 0:
            root.right_child = array_to_bitree(array[mid + 1:])
    return root