Design

1. Serialize and Deserialize BST

# Serialize and Deserialize BST

# Serialization：converting a data structure or object into a sequence of bits 
# so that it can be stored in a file or memory buffer, 
# or transmitted across a network connection link 
# to be reconstructed later in the same or another computer environment.

# Design an algorithm to serialize and deserialize a binary search tree. 
# There is no restriction on how your serialization/deserialization algorithm should work. 
# You just need to ensure that a binary search tree can be serialized to a string 
# and this string can be deserialized to the original tree structure.

# The encoded string should be as compact as possible.

class Codec:
    def serialize(self, root):
        def preorder(node):
            if node:
                vals.append(str(node.val))  
                preorder(node.left)  # 递归深入
                preorder(node.right) # 回至本层深入右侧
        vals = []
        preorder(root) # 自根节点放入数组
        return ' '.join(vals) #变成串儿
    
    def deserialize(self, data):
        preorder=list(data.split()) #串儿-数组
        inorder = sorted(preorder)  #前序；排序得中序
        return self.buildTree(preorder, inorder) #前序&中序 建树
    
    def buildTree(self, preorder, inorder):
        if inorder:
            ind = inorder.index(preorder.pop(0)) # 找寻根节点 左右分割分别
            root = TreeNode(inorder[ind])
            root.left = self.buildTree(preorder, inorder[0:ind])
            root.right = self.buildTree(preorder, inorder[ind+1:])
            return root

2. Serialize and Deserialize Binary Tree

# 297. Serialize and Deserialize Binary Tree
class Codec:
    def serialize(self,root):
        def doit(node): # 每次调用 传入节点
            if node:
                vals.append(str(node.val)) # 要转字符
                doit(node.left)  #左右也是处理节点
                doit(node.right) 
            else:
                vals.append('#') # 至叶子节点 标记一条路径
        vals=[] #
        doit(root)
        return ' '.join(vals) # 迭代生成整棵树的数组 转为串儿
    
    def deserialize(self,data):
        def doit():  # 没有参数 next迭代生成参数 参数不能直接传递 是需要next方法生成 
            val=next(vals) # next读取/生成当前节点字符 Python直接用变量不用定义
            if val=='#': return None # Tree的叶子结点一条路径结束 
            node=TreeNode(val) # Tree的生成
            node.left=doit() #因为递归 一条终结 可以继续上一层的doit
            node.right=doit()
            return node
        # 递归方法封起来 在反序列中递归调用该方法
        vals=iter(data.split()) #迭代对象为每个节点字符
        return doit()

3. Implement Trie (Prefix Tree)

# 208. Implement Trie (Prefix Tree)
# Implement a trie with insert, search, and startsWith methods.

from collections import defaultdict
class TrieNode(object):
    def __init__(self):
        self.nodes = defaultdict(TrieNode)  # Easy to insert new node.
        self.isword = False  # True for the end of the trie.
        
class Trie(object):
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        curr = self.root
        for char in word:
            curr = curr.nodes[char]
        curr.isword = True

    def search(self, word):
        curr = self.root
        for char in word:
            if char not in curr.nodes:
                return False
            curr = curr.nodes[char]
        return curr.isword

    def startsWith(self, prefix):
        curr = self.root
        for char in prefix:
            if char not in curr.nodes:
                return False
            curr = curr.nodes[char]
        return True

4. LRU Cache

# @des:   LRU(最近最少使用) 缓存机制
# OrderedDict 参看 https://docs.python.org/3/library/collections.html#collections.OrderedDict
class LRUCache:
    def __init__(self, capacity: int):
        self.dic = collections.OrderedDict()    # OrderedDict 记住了字典元素的添加顺序
        self.remain = capacity # 容量 大小
    def get(self, key: int) -> int:
        if key not in self.dic:
            return -1
        v = self.dic.pop(key)
        self.dic[key] = v # 被获取 刷新最近使用
        return v    
    def put(self, key: int, value: int) -> None:
        if key in self.dic:
            self.dic.pop(key) # 如果字典中有先弹出 再加入
        else: # 没有
            if self.remain > 0: # 字典未满
                self.remain -= 1 # 剩余容量 -1
            else: #  字典已满 弹出最近最少使用的，最老的元素
                self.dic.popitem(last = False)
                '''
                popitem(last=True)
                The popitem() method for ordered dictionaries returns and removes a (key, value) pair. 
                The pairs are returned in LIFO order if last is true or FIFO order if false.
                '''
        self.dic[key] = value