遍历

  1. 其实只有数据没有结构，这些都是一样的，数组即链表即二叉树，数组是格子排列，链表像是珍珠项链，二叉树就是砍成了两半的珍珠项链，n叉就是图。

  2. 前中后序列三种都只是顺序而已（具体来说，前序即快排后序即归并排），数组链表都可以有前中后顺序。什么涉及到顺序呢，但凡有递归就有这种顺序问题，为什么递归就会有顺序问题：就像是盗梦空间，有些操作你得在离开前，有些得在下层改变之后。

  3. 因此，数组链表二叉树图的遍历都相似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 递归遍历单链表
def traverse(head: ListNode):
    if head == None:
        return
    # 前序位置
    traverse(head.next)
    # 后序位置
    
# 递归遍历数组
def traverse(arr: List[int], i: int):
    if i == len(arr):
        return
    # 前序位置
    traverse(arr, i + 1)
    # 后序位置

框架来自大量网络资料及labuladong算法笔记以及自己的理解。主打简化再简化以便于能记住