代码随想录训练营第14天|二叉树前中后序遍历

二叉树的前序、中序和后序遍历各自有不同的应用场景，它们在计算机科学的多个领域中被广泛使用。

下面是这些遍历方法的一些主要应用：

前序遍历（根-左-右）

1. 创建拷贝：前序遍历可以用于创建二叉树的拷贝。遍历时，可以复制每个节点并递归地复制它的左右子树。
2. 打印树结构：前序遍历非常适合打印一个树的结构，尤其是当你想要显示树的层级结构时。因为你首先访问根节点，然后是左子树和右子树，这自然地反映了树的层次结构。
3. 表达式树：在解析算术或逻辑表达式时，前序遍历可以用来生成前缀表示法（也称为波兰表示法）。

中序遍历（左-根-右）

1. 二叉搜索树（BST）的排序输出：对于二叉搜索树，中序遍历将按照升序访问所有节点。这是因为二叉搜索树的性质确保了左子节点的值小于根节点的值，根节点的值小于右子节点的值。
2. 计算表达式：对于表达式树，中序遍历可以用来生成中缀表示法，这是人类最常用的算术和逻辑表达式表示法。

后序遍历（左-右-根）

1. 释放或删除树：后序遍历是删除或释放树节点的理想选择，因为你总是先删除子节点，最后删除父节点。这确保了在删除节点时，没有任何节点遗留未处理。
2. 后缀表达式：对于表达式树，后序遍历可以生成后缀表示法（也称为逆波兰表示法），这在某些计算场景下非常有用，如编译器中的表达式求值。
3. 依赖解析：在一些包含依赖关系的场景中（例如，项目的构建系统，或者是在进行软件安装时解析依赖库），后序遍历可以确保在处理当前项之前，所有依赖项都已经被处理。

综合应用

• 树的比较：通过比较两棵树的前序、中序或后序遍历的结果，我们可以判断两棵树是否相同（或者是否镜像对称等）。
• 路径和问题：在求解路径和问题时，前序遍历允许你在访问子节点之前处理根节点，这样可以在遍历的过程中累积路径和，并判断是否满足特定条件。
• 解析树结构：在一些需要解析树结构的应用中（如XML解析、文件系统遍历等），不同的遍历方法可以应对不同的解析需求。

每种遍历方法提供了一种不同的视角来查看树的结构，其选择取决于特定应用的需求。

# 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 []
        
        # 中序遍历：左 -> 根 -> 右
        res = []
        res.append(root.val)  # 访问根节点
        res += self.preorderTraversal(root.left)  # 访问左子树
        res += self.preorderTraversal(root.right)  # 访问右子树
        
        return res

# 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 is None:
            return []
        res = []
        res += self.postorderTraversal(root.left)
        res += self.postorderTraversal(root.right)
        res.append(root.val)

        return res

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