144. 二叉树的前序遍历

题目链接：144. 二叉树的前序遍历

题目描述

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

核心思考：深度优先搜索 (DFS)

二叉树的前序遍历遵循 “根 -> 左 -> 右” 的顺序。这是一种典型的深度优先搜索。

1. 递归逻辑：当访问到一个节点时，首先将其值记录到结果列表中，然后递归地处理其左子树，最后递归地处理其右子树。
2. 基准情形：如果当前节点为空，则直接返回，不进行任何处理。

虽然前序遍历也可以通过迭代（模拟栈）来高效实现，但递归写法因其简洁直观的特点，仍然是理解树遍历的基础。

解题思路 (Python)

# 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]:
        res = []
        
        def dfs(node):
            if not node:
                return
            # 前序：根 -> 左 -> 右
            res.append(node.val)
            dfs(node.left)
            dfs(node.right)
            
        dfs(root)
        return res

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是二叉树的节点数。每个节点被访问且处理且仅处理一次。
• 空间复杂度：$O(H)$，其中 $H$ 是树的高度。主要由递归调用的栈空间产生。平均情况下高度平衡的树为 $O(\log N)$，最坏情况（退化为链）下为 $O(N)$。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

val1 val2 val3 ... valN

输入一行整数数组表示二叉树的层序遍历，None 表示空节点。

完整代码：

import sys

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

def build_tree(arr):
    if not arr or arr[0] is None:
        return None
    root = TreeNode(arr[0])
    queue = [root]
    i = 1
    while queue and i < len(arr):
        node = queue.pop(0)
        if arr[i] is not None:
            node.left = TreeNode(arr[i])
            queue.append(node.left)
        i += 1
        if i < len(arr) and arr[i] is not None:
            node.right = TreeNode(arr[i])
            queue.append(node.right)
        i += 1
    return root

def tree_to_list(root):
    if not root:
        return []
    result = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)
    while result and result[-1] is None:
        result.pop()
    return result

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

            def dfs(node):
                if not node:
                    return
                # 前序：根 -> 左 -> 右
                res.append(node.val)
                dfs(node.left)
                dfs(node.right)

            dfs(root)
            return res

def main():
    arr = sys.stdin.read().strip().split()
    tree_arr = [None if v == 'None' else int(v) for v in arr]
    root = build_tree(tree_arr)

    sol = Solution()
    result = sol.preorderTraversal(root)
    print(result)

if __name__ == "__main__":
    main()