递归算法

前序遍历代码运行过程：

    A
   / \
  B   C
 / \   \
D   E   F
def preorder_traversal(root):
    if root:
        print(root.value, end=' ')  # 访问根节点
        preorder_traversal(root.left)  # 递归遍历左子树
        preorder_traversal(root.right)  # 递归遍历右子树
####################################
现在，让我们一步一步地看代码是如何运行的：
1.从根节点 A 开始。
2.打印根节点的值 A。
3.递归地遍历左子树，即以 B 为根的子树。
4.打印节点 B 的值。
5.递归地遍历 B 的左子树，即以 D 为根的子树。
6.打印节点 D 的值。
7.D 没有子节点，递归结束。
8.回到节点 B，递归地遍历其右子树，即以 E 为根的子树。
9.打印节点 E 的值。
10.E 没有子节点，递归结束。
11.回到节点 A，递归地遍历其右子树，即以 C 为根的子树。
12.打印节点 C 的值。
13.递归地遍历 C 的左子树，但 C 没有左子树。
14.递归地遍历 C 的右子树，即以 F 为根的子树。
15.打印节点 F 的值。
16.F 没有子节点，递归结束。
整个遍历过程结束。
#########################################

写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！

1. 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

2. 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

3. 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

144. 二叉树的前序遍历

# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        result = []
        result.append(root.val)  # 先访问根节点
        result.extend(self.preorderTraversal(root.left))  # 递归遍历左子树
        result.extend(self.preorderTraversal(root.right))  # 递归遍历右子树
        return result

145. 二叉树的后序遍历

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

def postorderTraversal(root):
    if root is None:
        return []
    result = []
    result.extend(postorderTraversal(root.left))  # 递归遍历左子树
    result.extend(postorderTraversal(root.right))  # 递归遍历右子树
    result.append(root.val)  # 最后访问根节点
    return result

# 示例用法
# 构造二叉树
'''
    1
   / \
  2   3
 / \
4   5
'''
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# 后序遍历
print("后序遍历结果：", postorderTraversal(root))  # 输出：[4, 5, 2, 3, 1]

94. 二叉树的中序遍历

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        ret = []
        ret.extend(self.inorderTraversal(root.left))
        ret.append(root.val)
        ret.extend(self.inorderTraversal(root.right))
        return ret

前序遍历（迭代法）

我们先看一下前序遍历。

前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。

为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。

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

def preorderTraversal(root):
    if root is None:
        return []
    
    result = []
    stack = [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

# 示例用法
# 构造二叉树
'''
    1
   / \
  2   3
 / \
4   5
'''
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# 前序遍历
print("前序遍历结果：", preorderTraversal(root))  # 输出：[1, 2, 4, 5, 3]

中序遍历（迭代法）

# 中序遍历-迭代-LC94_二叉树的中序遍历
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        stack = []  # 不能提前将root结点加入stack中
        result = []
        cur = root
        while cur or stack:
            # 先迭代访问最底层的左子树结点
            if cur:     
                stack.append(cur)
                cur = cur.left		
            # 到达最左结点后处理栈顶结点    
            else:		
                cur = stack.pop()
                result.append(cur.val)
                # 取栈顶元素右结点
                cur = cur.right	
        return result

后序遍历（迭代法）

# 后序遍历-迭代-LC145_二叉树的后序遍历
class Solution:
   def postorderTraversal(self, root: TreeNode) -> List[int]:
       if not root:
           return []
       stack = [root]
       result = []
       while stack:
           node = stack.pop()
           # 中结点先处理
           result.append(node.val)
           # 左孩子先入栈
           if node.left:
               stack.append(node.left)
           # 右孩子后入栈
           if node.right:
               stack.append(node.right)
       # 将最终的数组翻转
       return result[::-1]