[二叉树的前序遍历](https://leetcode.cn/problems/binary-tree-preorder-traversal/description/) ## 题目描述 给你二叉树的根节点 root，返回它节点值的前序遍历结果。 前序遍历的定义：访问根节点 → 遍历左子树 → 遍历右子树 **示例** ```text 输入：root = [1,null,2,3] 输出：[1,2,3] 1 \ 2 / 3 ``` ```text 1 / \ 2 3 / \ \ 4 5 6 前序遍历顺序：1 → 2 → 4 → 5 → 3 → 6 ``` ```text 输入：root = [] 输出：[] ``` ## 解题思路 核心思想是：先访问当前节点，再递归地访问左子树和右子树。 **关注遍历执行的顺序: `根左右`** ```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]: values = [] def dfs( root_ ): if not root_: return values.append( root_.val ) dfs( root_.left ) dfs( root_.right ) dfs( root ) return values ``` **时间复杂度: `O(n)`** **空间复杂度: `O(h)`** n = 节点总数 h = 树的高度 ( 最坏情况`O(n)` 最好情况`O(log n)` )