递归遍历

要理解递归，可以借助二叉树的递归遍历来理解。下面是二叉树递归遍历，以这个为例，来阐述下递归的原理。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def universalTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def dfs(cur: Optional[TreeNode]):
            # 1
            if not cur:
                return 
            # 1
            dfs(cur.left)
            # 2
            dfs(cur.right)
            # 3
        dfs(root)

原理

如上所示,dfs是一个递归函数，它表示以某个节点开始深度搜索（包含它及其子树）。而universalTraversal传入参数root并调用dfs，表示深度搜索root为根的这棵树。那么，如何理解这个dfs呢？注意到代码注释出的1，2，3,它们表示当前节点的调用时机，其中1是指刚刚遍历到当前节点时，2是指刚刚从该节点的左子树返回时，3时指刚刚从这个节点的右子树返回时。某个节点执行当层的dfs时，一共可以处理当前节点的时机就是这三个位置。

那么，何为递归呢？我的理解是，‘递’就是向下搜索的过程，比如上述遍历中，向左，右子树遍历就是‘递’，而从左，右子树返回就是归（2，3位置）。而我们不可能无限的'递'下去，总有一个尽头，这就引入了递归基或者说终止条件。什么是递归基呢？就是'递'到最后（有些问题是到叶子节点可以解决，有些问题是到叶子节点的左右子节点（空）可以解决），上例中的语句就是cur为空的时候直接返回。 所以由前面的思考可知，我们可以将一个原问题拆分为子问题，然后继续向下拆分，直到拆分到能够直接解决的问题，再一层层返回上面。这也是树形DP的基础。

此外，我们知道使用递归实际上隐藏了一个数据结构，就是在递的过程中会进行函数的压栈，归的过程中之前的函数返回，即出栈，直到当前层的递归函数。因此递归遍历使用迭代法实现时，一定离不开栈。

如何使用递归

那么在实际应用中，我们应该如何使用递归呢？实际上，只需要确定单层递归的逻辑和确定递归基。确定单层递归的逻辑，就是考虑当前节点或者当前的问题，如何分解为规模相当的子问题，然后将结果收集到作用域更大的变量（通过更大范围的变量如列表收集遍历过程中的所有所需信息）或者当前层的递归函数中（返回结果，以便继续给上层递归函数使用）。确定递归基就是确定终止条件。
以先序遍历为例，实际上就是上述通用遍历中，多了个列表记录节点的过程，只是节点处理（加入到列表中）的时机是第一次访问到节点的时候，即根左右。中序后序只是处理节点的时机不同，不再赘述。

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        def dfs(cur: Optional[TreeNode]):
            # 1
            if not cur:
                return 
            # 1
            res.append(cur.val)
            # 1
            dfs(cur.left)
            # 2
            dfs(cur.right)
            # 3
        
        dfs(root)
        return res

递归遍历如何用迭代

因为每个加入的节点不是遇到就处理，而是可能在之后才处理（即使是先序，之前加入的某节点的右节点也是在该节点的左子树处理完后才处理的），所以使用栈来实现。

先序遍历

栈不为空时，先加入右节点，再加入左节点。保证出栈时顺序为左右

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        res = []
        stack = []
        stack.append(root)
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return res

后序遍历

后序遍历为 左右根 ，与根右左逆序，观察顺序，先序遍历为根左右，因此利用先序遍历的代码做简单调整即可。

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        res = []
        stack = []
        stack.append(root)
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        res[:] = res[::-1]        
        return res

中序遍历

1 加入到栈中，一直遍历到最左
2 处理当前元素（当前最左），转向最左的右子树，重复1

栈为空只可能是初始状态和结束状态。

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        res = []
        stack = []
        while(stack or root):
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                res.append(root.val)
                root = root.right
        return res

层序遍历

层序遍历一层一层的遍历节点，采用的辅助结构是队列。之前的先中后序遍历对应dfs，而层序遍历对应的是bfs。
队列不为空时处理整体，size用来处理每层（知道当前层的个数)

def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root: return []
        res = []
        from collections import deque
        queue = deque()    
        queue.appendleft(root)
        while queue:
            size = len(queue)
            layerNodes = []
            while size:  
                node = queue.popleft()
                layerNodes.append(node.val)
                size = size-1
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(layerNodes)
        return res