Python二叉树怎么定义_树节点类与前中后序遍历递归实现-Python教程-PHP中文网

二叉树节点类定义为：class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val; self.left = left; self.right = right；val常用int或None，left/right默认None，不设空列表等非法默认值。

python二叉树怎么定义_树节点类与前中后序遍历递归实现

怎么定义二叉树节点类（Python）

二叉树不是 Python 内置类型，必须自己写 TreeNode 类。核心就三点：值、左子节点、右子节点——其他都是干扰项。

常见错误是把 left 或 right 默认设成 []、{} 或空字符串，这会导致后续判断逻辑混乱，比如 if node.left: 在 left 是空列表时也成立，但空列表不是合法子树。

val 通常用 int 或 None，不建议用默认值掩盖缺失
left 和 right 默认为 None，这是最安全的初始状态
别加多余属性（如 parent、height），除非真需要；加了就得同步维护，容易出错

示例：

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

前序/中序/后序遍历递归怎么写（无返回值版）

三者结构几乎一样，只差一行打印或处理的位置。关键不是记顺序，而是理解“当前节点该在什么时候被访问”。

容易踩的坑是递归终止条件写成 if not node.val:——节点值可以是 0、False、""，但节点本身非空；正确写法永远是 if not node:。

前序：先处理 node.val，再递归 node.left，最后 node.right
中序：先递归 node.left，再处理 node.val，最后 node.right
后序：先递归 node.left 和 node.right，最后处理 node.val

示例（中序）：

def inorder(root):
    if not root:  # ← 终止条件只看节点是否存在
        return
    inorder(root.left)
    print(root.val)  # ← 这里是中序的“中间”
    inorder(root.right)

返回遍历结果列表时要注意什么

如果函数要返回 list（比如力扣题型），不能在每次递归里新建列表再拼接，否则时间复杂度会退化到 O(n²)。

python-testing-patterns

使用 pytest、fixtures、mock 和测试驱动开发实现全面的测试策略。用于编写 Python 测试、搭建测试套件或实施测试最佳实践。

下载

更常见的错误是写成 return [root.val] + inorder(root.left) + inorder(root.right)——这会产生大量中间列表对象，小树看不出问题，树深一点就明显卡顿。

推荐用一个外部列表（如 res = []）传入递归函数，所有节点追加进去
或者用生成器（yield），适合大数场景，但调用方得用 list() 包一层
别依赖 __add__ 拼列表，Python 列表的 + 是拷贝操作

示例（前序，返回 list）：

def preorder_list(root):
    res = []
    def dfs(node):
        if not node:
            return
        res.append(node.val)
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return res