6.1二叉树的递归遍历（LC144,LC15,LC94）

什么是递归函数？

递归函数是一种函数调用自身的编程技巧。

在递归函数中，函数通过不断调用自身来解决一个问题，直到达到基本情况（递归终止条件）并返回结果。

 递归函数在解决一些问题时非常有用，特别是那些具有递归结构的问题，例如树、图等。通过使用递归函数，可以简化问题的表达和解决过程。 需要注意的是，在编写递归函数时，确保递归终止条件能够被满足，并且每次递归调用都能使问题规模减小，以避免无限递归和栈溢出等问题。此外，递归函数的性能可能不如迭代方式，因此在某些情况下，考虑使用迭代方法来替代递归。

递归的实现原理

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

递归算法三要素

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

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

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

树的定义（自己要会写！）

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

二叉树的前序遍历（VLR）

# 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
#VLR
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root == None:
            return []
        else:
            left = self.preorderTraversal(root.left)
            right = self.preorderTraversal(root.right)
            return [root.val] + left + right

二叉树的中序遍历（LVR）

# 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
#VLR
# 中序遍历-递归-LC94_二叉树的中序遍历
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if root == None:
            return []
        else:
            left = self.inorderTraversal(root.left)
            right = self.inorderTraversal(root.right)
            return  left + [root.val] + right

二叉树的后序遍历（LRV）

# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root == None:
            return []
        else:
            left = self.postorderTraversal(root.left)
            right = self.postorderTraversal(root.right)
            return  left + right + [root.val]