1. 创建二叉树、前中后序/深度/广度遍历

class TreeNode(object):
    def __init__(self, val, l=None, r=None):
        self.val = val
        self.lchild = l
        self.rchild = r

class Tree(object):
    def __init__(self, root=None):
        if not isinstance(root, TreeNode):
            root = TreeNode(root)
        self.root = root

    def add(self, node):
        if not isinstance(node, TreeNode):
            node = TreeNode(node)

        # root为None的情况
        if self.root == None:
            self.root = node
            return self

        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)
            if not cur_node.lchild:
                cur_node.lchild = node
                return self
            else:
                queue.append(cur_node.lchild)

            if not cur_node.rchild:
                cur_node.rchild = node
                return self
            else:
                queue.append(cur_node.rchild)

    # 广度遍历
    def breadth_travel(self):
        if self.root is None:
            return
        queue = [self.root]
        while queue:
            cur_node = queue.pop(0)  # 从root开始
            print(cur_node.val)
            if cur_node.lchild:  # 该节点的左
                queue.append(cur_node.lchild)
            if cur_node.rchild:  # 该节点的右
                queue.append(cur_node.rchild)

    # 深度遍历，同样的代码递归流程。三个环节位置 -> 三种遍历方式（获取值）
    # 1.前序遍历（先遍历树节点，然后遍历左节点，再遍历右节点）
    def preorder(self, node: TreeNode):
        if not node:
            return
        print(node.val)  # 父节点：root开始
        self.preorder(node.lchild)  # 开始挖左
        self.preorder(node.rchild)  # 最左挖到叶子节点，才来到此行挖右

    # 2.中序遍历（先遍历左节点，然后遍历父节点，再遍历右节点）
    def inorder(self, node: TreeNode):
        if not node:
            return
        self.inorder(node.lchild)  #
        print(node.val)
        self.inorder(node.rchild)  # 进入右节点

    # 3.后序遍历
    def protorder(self, node: TreeNode):
        if not node:
            return
        self.protorder(node.lchild)
        self.protorder(node.rchild)
        print(node.val) # 关键点

# 深度遍历
def dfs(node):
    def _dfs(node):
        if node is None: return
        print(node.val)
        _dfs(node.lchild)
        _dfs(node.rchild)
    _dfs(node.root)
# 广度遍历
def bfs(node):
    if node.root is None: return
    queue = [node.root]
    while queue:
        cur_node = queue.pop(0)  # 从root开始
        print(cur_node.val) # 获取到的值
        if cur_node.lchild:  # 该节点的左
            queue.append(cur_node.lchild)
        if cur_node.rchild:  # 该节点的右
            queue.append(cur_node.rchild)
# UT
tree = Tree(0).add(1).add(2).add(3).add(4).add(5).add(6).add(7).add(8).add(9)
print('前序遍历')
tree.preorder(tree.root)
print('中序遍历')
tree.inorder(tree.root)
print('后序遍历')
tree.protorder(tree.root)
print('深度遍历')
dfs(tree)
print('广度遍历')
bfs(tree)

2. 是否为相同树

class TreeNode(object):
    def __init__(self, val, l=None, r=None):
        self.val = val
        self.left = l
        self.right = r

class Solution:
    # 深度遍历法
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        # 全部同时为空，则一模一样
        if not p and not q:
            return True
        # 只有一个为空，则不一样
        elif not p or not q:
            return False
        # 如果节点值不一样，则不一样
        elif p.val != q.val:
            return False
        else:
            # 深度遍历代码
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

# UT
tree1 = TreeNode(1,TreeNode(2,TreeNode(4),TreeNode(5),),TreeNode(3,TreeNode(6),TreeNode(7)))
tree2 = TreeNode(1,TreeNode(2,TreeNode(4),TreeNode(5),),TreeNode(3,TreeNode(6),TreeNode(7)))
tree3 = TreeNode(1,TreeNode(2,TreeNode(3),TreeNode(4),),TreeNode(5,TreeNode(6),TreeNode(7)))
print(Solution().isSameTree(tree1,tree2)) # True
print(Solution().isSameTree(tree1,tree3)) # False

3. 翻转二叉树

# 翻转二叉树（交换左右节点）
def invertTree(root: TreeNode) -> TreeNode:
    return None if not root else TreeNode(root.val, invertTree(root.rchild), invertTree(root.lchild))
# 翻转树
invert_tree = invertTree(tree.root)

4. 打印链表

from typing import List
class ListNode():
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

class Solution:
    # 反转链表
    def reverseList(head: ListNode) -> ListNode:
        last = None
        while head:
            head.next, last, head = last, head, head.next
        return last
    # 顺序打印链表
    def printList(self,head: ListNode) -> List[int]:
        res = []
        while head:
            res.append(head.val)
            head = head.next
        return res
# UT
lst = ListNode(0,ListNode(1,ListNode(2,ListNode(3,ListNode(4)))))
print(Solution().printList(lst)) # 顺打印
print(Solution().printList(lst)[::-1]) # 反向打印

5. 删除排序链表中的重复元素

class ListNode():
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

def delDuplicates(head: ListNode) -> ListNode:
    node = head
    while node and node.next:
        if node.val == node.next.val:
            node.next = node.next.next
        else:
            node = node.next
    return head

6. 合并二个有序链表

class ListNode():
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
# 方法一：递归 O(N+M)O(N+M)
def mergeList(l1: ListNode, l2: ListNode):
    if not l1: return l2
    if not l2: return l1

    if l1.val <= l2.val:
        l1.next = mergeList(l1.next,l2)
        return l1
    else:
        l2.next = mergeList(l1,l2.next)
        return l2
# 方法二：迭代 O(N+M)O(1)
def mergeList2(l1: ListNode, l2: ListNode):
    tmp = ListNode(-1)
    prev = tmp
    while l1 and l2:
        if l1.val <= l2.val:
            prev.next = l1
            l1 = l1.next
        else:
            prev.next = l2
            l2 = l2.next            
        prev = prev.next
    # 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
    prev.next = l1 if l1 is not None else l2
    return tmp.next

7. 二叉树中最近的公共父节点

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

    def lowestCommonAncestor(root, p, q):
        if not root: return root
        if root.val == p.val or root.val == q.val: return root
        l = self.lowestCommonAncestor(root.left, p, q)
        r = self.lowestCommonAncestor(root.right, p, q)
        if l and r: return root
        if l: return l
        if r: return r

8. 重建二叉树

from typing import List

class TreeNode:
    def __init__(self, x, l=None, r=None):
        self.val = x
        self.left = l
        self.right = r

class Solution:
    # 通过前序、中序
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:

        if len(preorder) ==0:
            return None
        root_val = preorder[0]
        i = 0
        while inorder[i] != root_val:
            i += 1
        left_tree = self.buildTree(preorder[1:i+1], inorder[:i]) if i > 0 else None
        right_tree = self.buildTree(preorder[i+1:],inorder[i+1:]) if i < len(preorder) else None

        root = TreeNode(root_val)
        root.left = left_tree
        root.right = right_tree
        return root

9. 两个栈实现队列

class Queue:
    def __init__(self):
        self.a, self.b = [], []

    def appendTail(self, value: int) -> None:
        self.a.append(value)

    def deleteHead(self) -> int:
        if self.b:
            return self.b.pop()
        if not self.a:
            return -1
        while self.a:
            self.b.append(self.a.pop())
        return self.b.pop()