遍历法

• 核心是“遍历”
• 用外部变量 res 存结果
• 辅助函数主要负责访问节点

分解法

• 核心是“拆分问题”
• 递归函数直接返回结果
• 当前节点把左右子树结果合并

遍历法：通常会写一个辅助函数来遍历树，这个函数主要负责访问节点，结果一般存到外部变量 res 里。
如果是嵌套函数，递归调用时不用写 self.；如果是类里的普通方法，就要用 self. 调用递归。
最后调用辅助函数，并返回 res。要注意我们添加代码的位置是前中后的地方

分解法：（一般后用后续遍历，可以获取左右子树的返回数据）递归函数直接返回当前子树的结果，把左右子树的结果和当前节点合并起来，返回题目需要的值。
它既可以写成类方法，也可以写成嵌套函数，不一定非要用 self.。
如果题目还有额外条件，也可以配合辅助函数或额外变量一起处理。

1. 前序遍历

顺序：根 -> 左 -> 右

遍历法：需要多一个定义一个没有返回值的函数，用来遍历和外界的变量 res 列表，用来存储，然后调用函数，返回那个变量

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []

        def dfs(node):
            if node is None:
                return
            res.append(node.val)
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return res

分解法：一般不用嵌套函数，但是需要添加 self.函数名称（但也可以写成类里面的嵌套函数，不一定要用 self.），但是用 return 返回值，-当前节点把左右结果合起来，返回的是题目需要值或者变量。

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return [] #注意这有个空列表
        left = self.preorderTraversal(root.left)
        right = self.preorderTraversal(root.right)
        return [root.val] + left + right

2. 中序遍历

顺序：左 -> 根 -> 右

遍历法

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []

        def dfs(node):
            if node is None:
                return
            dfs(node.left)
            res.append(node.val)
            dfs(node.right)

        dfs(root)
        return res

分解法

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

3. 后序遍历

顺序：左 -> 右 -> 根

遍历法

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []

        def dfs(node):
            if node is None:
                return
            dfs(node.left)
            dfs(node.right)
            res.append(node.val)

        dfs(root)
        return res

分解法

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