二叉树前序遍历全解递归 DFS、迭代栈与 Morris 遍历LeetCode 144【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文以 LeetCode 144「二叉树的前序遍历」为核心系统讲解前序遍历的三种主流实现递归深度优先搜索DFS、借助显式栈的迭代 DFS以及空间复杂度为 O(1) 的 Morris 遍历。文章以 articles/binary-tree-preorder-traversal.md 为骨架并对照本仓库 python/0144-binary-tree-preorder-traversal.py、cpp/0144-binary-tree-preorder-traversal.cpp、java/0144-binary-tree-preorder-traversal.java、typescript/0144-binary-tree-preorder-traversal.ts 等源码逐一印证。读完本文你将掌握前序遍历的递归写法、栈模拟迭代写法以及不改树结构前提下的 Morris 线索化写法并能准确分析三者时间复杂度与空间复杂度的差异在面试与工程实践中根据约束条件做出正确选择。1. 问题定义与前序遍历规则给定一棵二叉树的根节点root返回其节点值的前序遍历结果。前序遍历的访问顺序是1. 当前节点本身 → 2. 左子树 → 3. 右子树仓库中 cpp/0144-binary-tree-preorder-traversal.cpp 的头部注释给出了最直观的例子Ex. Input: root [1,null,2,3] Output: [1,2,3]对根节点1先记录1其左子树为空再进入右子树节点2对2先记录其左孩子3先于右孩子访问于是得到序列[1, 2, 3]。前置知识Prerequisites动手实现前建议先熟悉以下三个基础点原文档将其列为 Prerequisites二叉树结构理解节点通过left、right两个指针连接的组织方式例如本仓库各语言中统一的TreeNode定义见下文各代码块的注释部分递归递归版 DFS 依赖函数调用栈call stack完成树的深入与回溯是理解前序遍历最简单直接的思维模型栈数据结构迭代版解法用显式栈模拟递归调用栈从而避免递归带来的栈溢出风险。2. 方法一递归深度优先搜索DFS直觉Intuition前序遍历的顺序是「节点 → 左子树 → 右子树」因此只要从根节点出发记录当前节点的值递归探索左孩子再递归探索右孩子。这一过程天然符合前序遍历的定义递归让系统自动处理树的层级结构与回溯。算法步骤Algorithm创建空结果列表res定义递归函数若node为null直接返回终止条件将node.val加入res递归处理node.left递归处理node.right从根节点root调用该函数返回res。多语言实现Python# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def preorderTraversal(self, root: Optional[TreeNode]) - List[int]: res [] def preorder(node): if not node: return res.append(node.val) preorder(node.left) preorder(node.right) preorder(root) return resJava/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { private ListInteger res; public ListInteger preorderTraversal(TreeNode root) { res new ArrayList(); preorder(root); return res; } private void preorder(TreeNode node) { if (node null) { return; } res.add(node.val); preorder(node.left); preorder(node.right); } }C/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { vectorint res; public: vectorint preorderTraversal(TreeNode* root) { preorder(root); return res; } private: void preorder(TreeNode* node) { if (!node) { return; } res.push_back(node-val); preorder(node-left); preorder(node-right); } };JavaScript/** * Definition for a binary tree node. * class TreeNode { * constructor(val 0, left null, right null) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { /** * param {TreeNode} root * return {number[]} */ preorderTraversal(root) { const res []; const preorder (node) { if (!node) return; res.push(node.val); preorder(node.left); preorder(node.right); }; preorder(root); return res; } }C#/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val0, TreeNode leftnull, TreeNode rightnull) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { public Listint PreorderTraversal(TreeNode root) { Listint res new Listint(); Preorder(root, res); return res; } private void Preorder(TreeNode node, Listint res) { if (node null) return; res.Add(node.val); Preorder(node.left, res); Preorder(node.right, res); } }Go/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func preorderTraversal(root *TreeNode) []int { res : []int{} var preorder func(node *TreeNode) preorder func(node *TreeNode) { if node nil { return } res append(res, node.Val) preorder(node.Left) preorder(node.Right) } preorder(root) return res }Kotlin/** * Example: * var ti TreeNode(5) * var v ti.val * Definition for a binary tree node. * class TreeNode(var val: Int) { * var left: TreeNode? null * var right: TreeNode? null * } */ class Solution { fun preorderTraversal(root: TreeNode?): ListInt { val res mutableListOfInt() fun preorder(node: TreeNode?) { if (node null) return res.add(node.val) preorder(node.left) preorder(node.right) } preorder(root) return res } }Swift/** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public var right: TreeNode? * public init() { self.val 0; self.left nil; self.right nil; } * public init(_ val: Int) { self.val val; self.left nil; self.right nil; } * public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) { * self.val val * self.left left * self.right right * } * } */ class Solution { func preorderTraversal(_ root: TreeNode?) - [Int] { var res [Int]() func preorder(_ node: TreeNode?) { guard let node node else { return } res.append(node.val) preorder(node.left) preorder(node.right) } preorder(root) return res } }Rust// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: OptionRcRefCellTreeNode, // pub right: OptionRcRefCellTreeNode, // } impl Solution { pub fn preorder_traversal(root: OptionRcRefCellTreeNode) - Veci32 { let mut res Vec::new(); Self::preorder(root, mut res); res } fn preorder(node: OptionRcRefCellTreeNode, res: mut Veci32) { if let Some(n) node { let n n.borrow(); res.push(n.val); Self::preorder(n.left, res); Self::preorder(n.right, res); } } }复杂度分析时间复杂度O(n)每个节点恰好被访问一次空间复杂度递归栈占用 O(n)最坏情况为链状树时栈深为 n平衡树时为 O(log n)此处按最坏上界记 O(n)结果数组占用 O(n)。仓库源码佐证仓库中的 cpp/0144-binary-tree-preorder-traversal.cpp 采用的正是「先记录、再递归左右子树」的递归写法且其注释明确标注了Time: O(N)、Space: O(H) - H Height of the binary tree与本文分析一致java/0144-binary-tree-preorder-traversal.java 与 typescript/0144-binary-tree-preorder-traversal.ts 亦为同一思路的递归实现可用于交叉验证。3. 方法二迭代深度优先搜索显式栈直觉Intuition前序遍历的模式依然是「访问节点 → 左 → 右」。用栈模拟递归时有一个关键技巧每访问一个节点立即记录其值前序遍历规则先压入右孩子再压入左孩子——因为栈是 LIFO后进先出先压入右孩子才能保证左孩子先被弹出处理当前指针移动到左孩子继续当左孩子为null时从栈中弹出节点继续处理右子树。这样无需递归即可完整还原前序序列。仓库中的 python/0144-binary-tree-preorder-traversal.py 正是这一写法的精简实现见下方 Python 代码块两者逻辑完全一致。算法步骤Algorithm初始化结果列表res创建空栈令cur root当cur不为null或栈非空时循环若cur存在将cur.val加入res将cur.right压入栈cur移动到cur.left否则从栈中弹出节点并赋给cur返回res。多语言实现Python# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def preorderTraversal(self, root: Optional[TreeNode]) - List[int]: res [] stack [] cur root while cur or stack: if cur: res.append(cur.val) stack.append(cur.right) cur cur.left else: cur stack.pop() return resJava/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { public ListInteger preorderTraversal(TreeNode root) { ListInteger res new ArrayList(); StackTreeNode stack new Stack(); TreeNode cur root; while (cur ! null || !stack.isEmpty()) { if (cur ! null) { res.add(cur.val); stack.push(cur.right); cur cur.left; } else { cur stack.pop(); } } return res; } }C/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vectorint preorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* stack; TreeNode* cur root; while (cur || !stack.empty()) { if (cur) { res.push_back(cur-val); stack.push(cur-right); cur cur-left; } else { cur stack.top(); stack.pop(); } } return res; } };JavaScript/** * Definition for a binary tree node. * class TreeNode { * constructor(val 0, left null, right null) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { /** * param {TreeNode} root * return {number[]} */ preorderTraversal(root) { const res []; const stack []; let cur root; while (cur || stack.length 0) { if (cur) { res.push(cur.val); stack.push(cur.right); cur cur.left; } else { cur stack.pop(); } } return res; } }C#/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val0, TreeNode leftnull, TreeNode rightnull) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { public Listint PreorderTraversal(TreeNode root) { Listint res new Listint(); StackTreeNode stack new StackTreeNode(); TreeNode cur root; while (cur ! null || stack.Count 0) { if (cur ! null) { res.Add(cur.val); stack.Push(cur.right); cur cur.left; } else { cur stack.Pop(); } } return res; } }Go/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func preorderTraversal(root *TreeNode) []int { res : []int{} stack : []*TreeNode{} cur : root for cur ! nil || len(stack) 0 { if cur ! nil { res append(res, cur.Val) stack append(stack, cur.Right) cur cur.Left } else { cur stack[len(stack)-1] stack stack[:len(stack)-1] } } return res }Kotlin/** * Example: * var ti TreeNode(5) * var v ti.val * Definition for a binary tree node. * class TreeNode(var val: Int) { * var left: TreeNode? null * var right: TreeNode? null * } */ class Solution { fun preorderTraversal(root: TreeNode?): ListInt { val res mutableListOfInt() val stack ArrayDequeTreeNode?() var cur root while (cur ! null || stack.isNotEmpty()) { if (cur ! null) { res.add(cur.val) stack.addLast(cur.right) cur cur.left } else { cur stack.removeLast() } } return res } }Swift/** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public var right: TreeNode? * public init() { self.val 0; self.left nil; self.right nil; } * public init(_ val: Int) { self.val val; self.left nil; self.right nil; } * public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) { * self.val val * self.left left * self.right right * } * } */ class Solution { func preorderTraversal(_ root: TreeNode?) - [Int] { var res [Int]() var stack [TreeNode?]() var cur root while cur ! nil || !stack.isEmpty { if cur ! nil { res.append(cur!.val) stack.append(cur?.right) cur cur?.left } else { cur stack.removeLast() } } return res } }Rustimpl Solution { pub fn preorder_traversal(root: OptionRcRefCellTreeNode) - Veci32 { let mut res Vec::new(); let mut stack: VecOptionRcRefCellTreeNode Vec::new(); let mut cur root; while cur.is_some() || !stack.is_empty() { if let Some(node) cur { let node_ref node.borrow(); res.push(node_ref.val); stack.push(node_ref.right.clone()); cur node_ref.left.clone(); } else { cur stack.pop().unwrap(); } } res } }复杂度分析时间复杂度O(n)每个节点恰好入栈/出栈一次空间复杂度栈空间 O(n)最坏情况下需容纳整条路径上的右子树引用结果数组 O(n)。仓库源码佐证python/0144-binary-tree-preorder-traversal.py 完整实现了本节的迭代栈思路class Solution: def preorderTraversal(self, root: Optional[TreeNode]) - List[int]: cur, stack root, [] res [] while cur or stack: if cur: res.append(cur.val) stack.append(cur.right) cur cur.left else: cur stack.pop() return res注意其中的顺序stack.append(cur.right)在前cur cur.left在后——先压右、后走左正是迭代前序遍历的核心稍后「常见错误」一节将专门讨论颠倒此顺序的后果。4. 方法三Morris 遍历O(1) 额外空间直觉IntuitionMorris 遍历可以在不使用递归、不使用栈的前提下完成前序遍历额外空间为O(1)。其核心思想是对每个存在左孩子的节点找到其中序前驱即左子树中最右侧的节点正常情况下遍历完左子树后需要回到当前节点既然没有栈来保存回溯信息就临时建立一条「线索」threadpredecessor.right current第一次到达某节点时立即记录其值因为前序 节点 → 左 → 右通过线索回到该节点后移除线索恢复树的原状然后继续处理右孩子。整个过程会临时修改树结构但遍历结束时树会被完整恢复。算法步骤Algorithm初始化cur root与结果列表res当cur不为null时循环若cur.left不存在访问cur将值加入res移动到cur.right否则找到中序前驱prevcur.left中最右侧的节点若prev.right为null这是第一次到达cur将cur.val加入res建立线索prev.right cur移动到cur.left否则线索已存在说明左子树遍历完毕正在返回移除线索prev.right None移动到cur.right返回res。多语言实现Python# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def preorderTraversal(self, root: Optional[TreeNode]) - List[int]: res [] cur root while cur: if not cur.left: res.append(cur.val) cur cur.right else: prev cur.left while prev.right and prev.right ! cur: prev prev.right if not prev.right: res.append(cur.val) prev.right cur cur cur.left else: prev.right None cur cur.right return resJava/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { public ListInteger preorderTraversal(TreeNode root) { ListInteger res new ArrayList(); TreeNode cur root; while (cur ! null) { if (cur.left null) { res.add(cur.val); cur cur.right; } else { TreeNode prev cur.left; while (prev.right ! null prev.right ! cur) { prev prev.right; } if (prev.right null) { res.add(cur.val); prev.right cur; cur cur.left; } else { prev.right null; cur cur.right; } } } return res; } }C/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vectorint preorderTraversal(TreeNode* root) { vectorint res; TreeNode* cur root; while (cur) { if (!cur-left) { res.push_back(cur-val); cur cur-right; } else { TreeNode* prev cur-left; while (prev-right prev-right ! cur) { prev prev-right; } if (!prev-right) { res.push_back(cur-val); prev-right cur; cur cur-left; } else { prev-right nullptr; cur cur-right; } } } return res; } };JavaScript/** * Definition for a binary tree node. * class TreeNode { * constructor(val 0, left null, right null) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { /** * param {TreeNode} root * return {number[]} */ preorderTraversal(root) { const res []; let cur root; while (cur) { if (!cur.left) { res.push(cur.val); cur cur.right; } else { let prev cur.left; while (prev.right prev.right ! cur) { prev prev.right; } if (!prev.right) { res.push(cur.val); prev.right cur; cur cur.left; } else { prev.right null; cur cur.right; } } } return res; } }C#/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val0, TreeNode leftnull, TreeNode rightnull) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { public Listint PreorderTraversal(TreeNode root) { Listint res new Listint(); TreeNode cur root; while (cur ! null) { if (cur.left null) { res.Add(cur.val); cur cur.right; } else { TreeNode prev cur.left; while (prev.right ! null prev.right ! cur) { prev prev.right; } if (prev.right null) { res.Add(cur.val); prev.right cur; cur cur.left; } else { prev.right null; cur cur.right; } } } return res; } }Go/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func preorderTraversal(root *TreeNode) []int { res : []int{} cur : root for cur ! nil { if cur.Left nil { res append(res, cur.Val) cur cur.Right } else { prev : cur.Left for prev.Right ! nil prev.Right ! cur { prev prev.Right } if prev.Right nil { res append(res, cur.Val) prev.Right cur cur cur.Left } else { prev.Right nil cur cur.Right } } } return res }Kotlin/** * Example: * var ti TreeNode(5) * var v ti.val * Definition for a binary tree node. * class TreeNode(var val: Int) { * var left: TreeNode? null * var right: TreeNode? null * } */ class Solution { fun preorderTraversal(root: TreeNode?): ListInt { val res mutableListOfInt() var cur root while (cur ! null) { if (cur.left null) { res.add(cur.val) cur cur.right } else { var prev cur.left while (prev?.right ! null prev.right ! cur) { prev prev.right } if (prev?.right null) { res.add(cur.val) prev?.right cur cur cur.left } else { prev.right null cur cur.right } } } return res } }Swift/** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public var right: TreeNode? * public init() { self.val 0; self.left nil; self.right nil; } * public init(_ val: Int) { self.val val; self.left nil; self.right nil; } * public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) { * self.val val * self.left left * self.right right * } * } */ class Solution { func preorderTraversal(_ root: TreeNode?) - [Int] { var res [Int]() var cur root while cur ! nil { if cur?.left nil { res.append(cur!.val) cur cur?.right } else { var prev cur?.left while prev?.right ! nil prev?.right ! cur { prev prev?.right } if prev?.right nil { res.append(cur!.val) prev?.right cur cur cur?.left } else { prev?.right nil cur cur?.right } } } return res } }Rust// Note: Morris Traversal modifies the tree in-place, which is not // directly possible with RcRefCellTreeNode in safe Rust without // unsafe code. This is a stack-based O(1)-extra-space simulation // that preserves the same algorithmic idea for LeetCode submission. impl Solution { pub fn preorder_traversal(root: OptionRcRefCellTreeNode) - Veci32 { let mut res Vec::new(); let mut stack Vec::new(); if let Some(r) root { stack.push(r); } while let Some(node) stack.pop() { let node_ref node.borrow(); res.push(node_ref.val); if let Some(ref right) node_ref.right { stack.push(right.clone()); } if let Some(ref left) node_ref.left { stack.push(left.clone()); } } res } }Rust 实现说明Morris 遍历需要原地修改树结构而在安全 Rust 的RcRefCellTreeNode模型下不使用unsafe代码无法直接实现指针式线索。因此仓库原文档同样如此处理采用一种「保持同一算法思想、额外空间 O(1)」的栈式模拟版本用于 LeetCode 提交。复杂度分析时间复杂度O(n)。每个节点最多被「找前驱」的过程经过常数次总体仍为线性空间复杂度额外空间 O(1)仅使用常数个指针变量结果数组 O(n)。5. 三种方法对比总结方法是否使用递归是否使用栈时间额外空间特点递归 DFS是否依赖调用栈O(n)O(n)递归栈代码最简洁、最符合直觉树过深时有栈溢出风险迭代 DFS显式栈否是O(n)O(n)栈避免递归栈溢出入栈顺序是关键Morris 遍历否否O(n)O(1)空间最优需临时修改树结构遍历后恢复三者时间均为 O(n)差异集中在额外空间与实现复杂度递归最易写、Morris 最难理解但空间最优。面试中通常先给出递归版本再演进到迭代版本只有被明确追问「能否做到 O(1) 额外空间」时才需要展开 Morris 遍历。6. 常见错误Common Pitfalls6.1 在递归完子节点之后才添加节点值前序遍历要求「先访问当前节点再访问其子节点」。若把res.append(node.val)放到左右子树的递归调用之后得到的就是后序遍历而非前序遍历# Wrong: this is postorder, not preorder preorder(node.left) preorder(node.right) res.append(node.val)判断口诀很简单值记录的位置决定了遍历类型——前序值 → 左 → 右、中序左 → 值 → 右、后序左 → 右 → 值的唯一区别就是这一行代码的位置。6.2 迭代写法中先压入左孩子在栈式迭代方案中必须先压右孩子、后压左孩子。因为栈是 LIFO若先压左孩子左孩子会先被弹出处理导致右子树被提前访问# Wrong: processes right subtree before left stack.append(cur.left) # should push right first stack.append(cur.right)正确的顺序一定是「先 push 右、再 push 左」这样左子树才能保持「先被处理」的前序遍历语义。可对照 python/0144-binary-tree-preorder-traversal.py 中stack.append(cur.right)与cur cur.left的书写顺序来校验自己的实现。6.3 Morris 遍历中忘记移除线索Morris 遍历若在「第二次到达」分支prev.right已指向cur忘记执行prev.right None树结构将残留临时线索导致后续访问逻辑错乱并破坏原树。务必保证每个建立线索的节点在遍历结束前都被恢复。7. 延伸阅读与本仓库相关资源本仓库 articles/README.md 说明了文章撰写规范每篇文章应包含与 NeetCode 视频一致的解法、时间与空间复杂度并尽可能覆盖全部相关解法——本文三种解法正符合这一要求。前序遍历与二叉树的另外两种基本遍历互为姊妹篇建议一并学习以建立完整的遍历体系二叉树中序遍历顺序为「左 → 节点 → 右」在二叉搜索树上输出有序序列同样包含递归、迭代与 Morris 三种解法二叉树后序遍历顺序为「左 → 右 → 节点」常用于自底向上的树形 DP 与删除/释放节点的场景从前序与中序遍历序列构造二叉树前序遍历的第一个元素就是根节点这一性质是「给定两种遍历重建二叉树」类题目的关键仓库中 cpp/0105-construct-binary-tree-from-preorder-and-inorder-traversal.cpp、python/0105-construct-binary-tree-from-preorder-and-inorder-traversal.py 等均有对应实现可作参考。掌握前序遍历后可进一步将其思想迁移到 N 叉树参见 c/0589-n-ary-tree-preorder-traversal.c以及序列化、复制树等需要「先处理父节点」的二叉树问题上。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 二叉树前序遍历全解：递归 DFS、迭代栈与 Morris 遍历（LeetCode 144）
二叉树前序遍历全解递归 DFS、迭代栈与 Morris 遍历LeetCode 144【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文以 LeetCode 144「二叉树的前序遍历」为核心系统讲解前序遍历的三种主流实现递归深度优先搜索DFS、借助显式栈的迭代 DFS以及空间复杂度为 O(1) 的 Morris 遍历。文章以 articles/binary-tree-preorder-traversal.md 为骨架并对照本仓库 python/0144-binary-tree-preorder-traversal.py、cpp/0144-binary-tree-preorder-traversal.cpp、java/0144-binary-tree-preorder-traversal.java、typescript/0144-binary-tree-preorder-traversal.ts 等源码逐一印证。读完本文你将掌握前序遍历的递归写法、栈模拟迭代写法以及不改树结构前提下的 Morris 线索化写法并能准确分析三者时间复杂度与空间复杂度的差异在面试与工程实践中根据约束条件做出正确选择。1. 问题定义与前序遍历规则给定一棵二叉树的根节点root返回其节点值的前序遍历结果。前序遍历的访问顺序是1. 当前节点本身 → 2. 左子树 → 3. 右子树仓库中 cpp/0144-binary-tree-preorder-traversal.cpp 的头部注释给出了最直观的例子Ex. Input: root [1,null,2,3] Output: [1,2,3]对根节点1先记录1其左子树为空再进入右子树节点2对2先记录其左孩子3先于右孩子访问于是得到序列[1, 2, 3]。前置知识Prerequisites动手实现前建议先熟悉以下三个基础点原文档将其列为 Prerequisites二叉树结构理解节点通过left、right两个指针连接的组织方式例如本仓库各语言中统一的TreeNode定义见下文各代码块的注释部分递归递归版 DFS 依赖函数调用栈call stack完成树的深入与回溯是理解前序遍历最简单直接的思维模型栈数据结构迭代版解法用显式栈模拟递归调用栈从而避免递归带来的栈溢出风险。2. 方法一递归深度优先搜索DFS直觉Intuition前序遍历的顺序是「节点 → 左子树 → 右子树」因此只要从根节点出发记录当前节点的值递归探索左孩子再递归探索右孩子。这一过程天然符合前序遍历的定义递归让系统自动处理树的层级结构与回溯。算法步骤Algorithm创建空结果列表res定义递归函数若node为null直接返回终止条件将node.val加入res递归处理node.left递归处理node.right从根节点root调用该函数返回res。多语言实现Python# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def preorderTraversal(self, root: Optional[TreeNode]) - List[int]: res [] def preorder(node): if not node: return res.append(node.val) preorder(node.left) preorder(node.right) preorder(root) return resJava/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { private ListInteger res; public ListInteger preorderTraversal(TreeNode root) { res new ArrayList(); preorder(root); return res; } private void preorder(TreeNode node) { if (node null) { return; } res.add(node.val); preorder(node.left); preorder(node.right); } }C/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { vectorint res; public: vectorint preorderTraversal(TreeNode* root) { preorder(root); return res; } private: void preorder(TreeNode* node) { if (!node) { return; } res.push_back(node-val); preorder(node-left); preorder(node-right); } };JavaScript/** * Definition for a binary tree node. * class TreeNode { * constructor(val 0, left null, right null) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { /** * param {TreeNode} root * return {number[]} */ preorderTraversal(root) { const res []; const preorder (node) { if (!node) return; res.push(node.val); preorder(node.left); preorder(node.right); }; preorder(root); return res; } }C#/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val0, TreeNode leftnull, TreeNode rightnull) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { public Listint PreorderTraversal(TreeNode root) { Listint res new Listint(); Preorder(root, res); return res; } private void Preorder(TreeNode node, Listint res) { if (node null) return; res.Add(node.val); Preorder(node.left, res); Preorder(node.right, res); } }Go/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func preorderTraversal(root *TreeNode) []int { res : []int{} var preorder func(node *TreeNode) preorder func(node *TreeNode) { if node nil { return } res append(res, node.Val) preorder(node.Left) preorder(node.Right) } preorder(root) return res }Kotlin/** * Example: * var ti TreeNode(5) * var v ti.val * Definition for a binary tree node. * class TreeNode(var val: Int) { * var left: TreeNode? null * var right: TreeNode? null * } */ class Solution { fun preorderTraversal(root: TreeNode?): ListInt { val res mutableListOfInt() fun preorder(node: TreeNode?) { if (node null) return res.add(node.val) preorder(node.left) preorder(node.right) } preorder(root) return res } }Swift/** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public var right: TreeNode? * public init() { self.val 0; self.left nil; self.right nil; } * public init(_ val: Int) { self.val val; self.left nil; self.right nil; } * public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) { * self.val val * self.left left * self.right right * } * } */ class Solution { func preorderTraversal(_ root: TreeNode?) - [Int] { var res [Int]() func preorder(_ node: TreeNode?) { guard let node node else { return } res.append(node.val) preorder(node.left) preorder(node.right) } preorder(root) return res } }Rust// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: OptionRcRefCellTreeNode, // pub right: OptionRcRefCellTreeNode, // } impl Solution { pub fn preorder_traversal(root: OptionRcRefCellTreeNode) - Veci32 { let mut res Vec::new(); Self::preorder(root, mut res); res } fn preorder(node: OptionRcRefCellTreeNode, res: mut Veci32) { if let Some(n) node { let n n.borrow(); res.push(n.val); Self::preorder(n.left, res); Self::preorder(n.right, res); } } }复杂度分析时间复杂度O(n)每个节点恰好被访问一次空间复杂度递归栈占用 O(n)最坏情况为链状树时栈深为 n平衡树时为 O(log n)此处按最坏上界记 O(n)结果数组占用 O(n)。仓库源码佐证仓库中的 cpp/0144-binary-tree-preorder-traversal.cpp 采用的正是「先记录、再递归左右子树」的递归写法且其注释明确标注了Time: O(N)、Space: O(H) - H Height of the binary tree与本文分析一致java/0144-binary-tree-preorder-traversal.java 与 typescript/0144-binary-tree-preorder-traversal.ts 亦为同一思路的递归实现可用于交叉验证。3. 方法二迭代深度优先搜索显式栈直觉Intuition前序遍历的模式依然是「访问节点 → 左 → 右」。用栈模拟递归时有一个关键技巧每访问一个节点立即记录其值前序遍历规则先压入右孩子再压入左孩子——因为栈是 LIFO后进先出先压入右孩子才能保证左孩子先被弹出处理当前指针移动到左孩子继续当左孩子为null时从栈中弹出节点继续处理右子树。这样无需递归即可完整还原前序序列。仓库中的 python/0144-binary-tree-preorder-traversal.py 正是这一写法的精简实现见下方 Python 代码块两者逻辑完全一致。算法步骤Algorithm初始化结果列表res创建空栈令cur root当cur不为null或栈非空时循环若cur存在将cur.val加入res将cur.right压入栈cur移动到cur.left否则从栈中弹出节点并赋给cur返回res。多语言实现Python# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def preorderTraversal(self, root: Optional[TreeNode]) - List[int]: res [] stack [] cur root while cur or stack: if cur: res.append(cur.val) stack.append(cur.right) cur cur.left else: cur stack.pop() return resJava/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { public ListInteger preorderTraversal(TreeNode root) { ListInteger res new ArrayList(); StackTreeNode stack new Stack(); TreeNode cur root; while (cur ! null || !stack.isEmpty()) { if (cur ! null) { res.add(cur.val); stack.push(cur.right); cur cur.left; } else { cur stack.pop(); } } return res; } }C/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vectorint preorderTraversal(TreeNode* root) { vectorint res; stackTreeNode* stack; TreeNode* cur root; while (cur || !stack.empty()) { if (cur) { res.push_back(cur-val); stack.push(cur-right); cur cur-left; } else { cur stack.top(); stack.pop(); } } return res; } };JavaScript/** * Definition for a binary tree node. * class TreeNode { * constructor(val 0, left null, right null) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { /** * param {TreeNode} root * return {number[]} */ preorderTraversal(root) { const res []; const stack []; let cur root; while (cur || stack.length 0) { if (cur) { res.push(cur.val); stack.push(cur.right); cur cur.left; } else { cur stack.pop(); } } return res; } }C#/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val0, TreeNode leftnull, TreeNode rightnull) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { public Listint PreorderTraversal(TreeNode root) { Listint res new Listint(); StackTreeNode stack new StackTreeNode(); TreeNode cur root; while (cur ! null || stack.Count 0) { if (cur ! null) { res.Add(cur.val); stack.Push(cur.right); cur cur.left; } else { cur stack.Pop(); } } return res; } }Go/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func preorderTraversal(root *TreeNode) []int { res : []int{} stack : []*TreeNode{} cur : root for cur ! nil || len(stack) 0 { if cur ! nil { res append(res, cur.Val) stack append(stack, cur.Right) cur cur.Left } else { cur stack[len(stack)-1] stack stack[:len(stack)-1] } } return res }Kotlin/** * Example: * var ti TreeNode(5) * var v ti.val * Definition for a binary tree node. * class TreeNode(var val: Int) { * var left: TreeNode? null * var right: TreeNode? null * } */ class Solution { fun preorderTraversal(root: TreeNode?): ListInt { val res mutableListOfInt() val stack ArrayDequeTreeNode?() var cur root while (cur ! null || stack.isNotEmpty()) { if (cur ! null) { res.add(cur.val) stack.addLast(cur.right) cur cur.left } else { cur stack.removeLast() } } return res } }Swift/** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public var right: TreeNode? * public init() { self.val 0; self.left nil; self.right nil; } * public init(_ val: Int) { self.val val; self.left nil; self.right nil; } * public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) { * self.val val * self.left left * self.right right * } * } */ class Solution { func preorderTraversal(_ root: TreeNode?) - [Int] { var res [Int]() var stack [TreeNode?]() var cur root while cur ! nil || !stack.isEmpty { if cur ! nil { res.append(cur!.val) stack.append(cur?.right) cur cur?.left } else { cur stack.removeLast() } } return res } }Rustimpl Solution { pub fn preorder_traversal(root: OptionRcRefCellTreeNode) - Veci32 { let mut res Vec::new(); let mut stack: VecOptionRcRefCellTreeNode Vec::new(); let mut cur root; while cur.is_some() || !stack.is_empty() { if let Some(node) cur { let node_ref node.borrow(); res.push(node_ref.val); stack.push(node_ref.right.clone()); cur node_ref.left.clone(); } else { cur stack.pop().unwrap(); } } res } }复杂度分析时间复杂度O(n)每个节点恰好入栈/出栈一次空间复杂度栈空间 O(n)最坏情况下需容纳整条路径上的右子树引用结果数组 O(n)。仓库源码佐证python/0144-binary-tree-preorder-traversal.py 完整实现了本节的迭代栈思路class Solution: def preorderTraversal(self, root: Optional[TreeNode]) - List[int]: cur, stack root, [] res [] while cur or stack: if cur: res.append(cur.val) stack.append(cur.right) cur cur.left else: cur stack.pop() return res注意其中的顺序stack.append(cur.right)在前cur cur.left在后——先压右、后走左正是迭代前序遍历的核心稍后「常见错误」一节将专门讨论颠倒此顺序的后果。4. 方法三Morris 遍历O(1) 额外空间直觉IntuitionMorris 遍历可以在不使用递归、不使用栈的前提下完成前序遍历额外空间为O(1)。其核心思想是对每个存在左孩子的节点找到其中序前驱即左子树中最右侧的节点正常情况下遍历完左子树后需要回到当前节点既然没有栈来保存回溯信息就临时建立一条「线索」threadpredecessor.right current第一次到达某节点时立即记录其值因为前序 节点 → 左 → 右通过线索回到该节点后移除线索恢复树的原状然后继续处理右孩子。整个过程会临时修改树结构但遍历结束时树会被完整恢复。算法步骤Algorithm初始化cur root与结果列表res当cur不为null时循环若cur.left不存在访问cur将值加入res移动到cur.right否则找到中序前驱prevcur.left中最右侧的节点若prev.right为null这是第一次到达cur将cur.val加入res建立线索prev.right cur移动到cur.left否则线索已存在说明左子树遍历完毕正在返回移除线索prev.right None移动到cur.right返回res。多语言实现Python# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def preorderTraversal(self, root: Optional[TreeNode]) - List[int]: res [] cur root while cur: if not cur.left: res.append(cur.val) cur cur.right else: prev cur.left while prev.right and prev.right ! cur: prev prev.right if not prev.right: res.append(cur.val) prev.right cur cur cur.left else: prev.right None cur cur.right return resJava/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { public ListInteger preorderTraversal(TreeNode root) { ListInteger res new ArrayList(); TreeNode cur root; while (cur ! null) { if (cur.left null) { res.add(cur.val); cur cur.right; } else { TreeNode prev cur.left; while (prev.right ! null prev.right ! cur) { prev prev.right; } if (prev.right null) { res.add(cur.val); prev.right cur; cur cur.left; } else { prev.right null; cur cur.right; } } } return res; } }C/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vectorint preorderTraversal(TreeNode* root) { vectorint res; TreeNode* cur root; while (cur) { if (!cur-left) { res.push_back(cur-val); cur cur-right; } else { TreeNode* prev cur-left; while (prev-right prev-right ! cur) { prev prev-right; } if (!prev-right) { res.push_back(cur-val); prev-right cur; cur cur-left; } else { prev-right nullptr; cur cur-right; } } } return res; } };JavaScript/** * Definition for a binary tree node. * class TreeNode { * constructor(val 0, left null, right null) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { /** * param {TreeNode} root * return {number[]} */ preorderTraversal(root) { const res []; let cur root; while (cur) { if (!cur.left) { res.push(cur.val); cur cur.right; } else { let prev cur.left; while (prev.right prev.right ! cur) { prev prev.right; } if (!prev.right) { res.push(cur.val); prev.right cur; cur cur.left; } else { prev.right null; cur cur.right; } } } return res; } }C#/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val0, TreeNode leftnull, TreeNode rightnull) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { public Listint PreorderTraversal(TreeNode root) { Listint res new Listint(); TreeNode cur root; while (cur ! null) { if (cur.left null) { res.Add(cur.val); cur cur.right; } else { TreeNode prev cur.left; while (prev.right ! null prev.right ! cur) { prev prev.right; } if (prev.right null) { res.Add(cur.val); prev.right cur; cur cur.left; } else { prev.right null; cur cur.right; } } } return res; } }Go/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func preorderTraversal(root *TreeNode) []int { res : []int{} cur : root for cur ! nil { if cur.Left nil { res append(res, cur.Val) cur cur.Right } else { prev : cur.Left for prev.Right ! nil prev.Right ! cur { prev prev.Right } if prev.Right nil { res append(res, cur.Val) prev.Right cur cur cur.Left } else { prev.Right nil cur cur.Right } } } return res }Kotlin/** * Example: * var ti TreeNode(5) * var v ti.val * Definition for a binary tree node. * class TreeNode(var val: Int) { * var left: TreeNode? null * var right: TreeNode? null * } */ class Solution { fun preorderTraversal(root: TreeNode?): ListInt { val res mutableListOfInt() var cur root while (cur ! null) { if (cur.left null) { res.add(cur.val) cur cur.right } else { var prev cur.left while (prev?.right ! null prev.right ! cur) { prev prev.right } if (prev?.right null) { res.add(cur.val) prev?.right cur cur cur.left } else { prev.right null cur cur.right } } } return res } }Swift/** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public var right: TreeNode? * public init() { self.val 0; self.left nil; self.right nil; } * public init(_ val: Int) { self.val val; self.left nil; self.right nil; } * public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) { * self.val val * self.left left * self.right right * } * } */ class Solution { func preorderTraversal(_ root: TreeNode?) - [Int] { var res [Int]() var cur root while cur ! nil { if cur?.left nil { res.append(cur!.val) cur cur?.right } else { var prev cur?.left while prev?.right ! nil prev?.right ! cur { prev prev?.right } if prev?.right nil { res.append(cur!.val) prev?.right cur cur cur?.left } else { prev?.right nil cur cur?.right } } } return res } }Rust// Note: Morris Traversal modifies the tree in-place, which is not // directly possible with RcRefCellTreeNode in safe Rust without // unsafe code. This is a stack-based O(1)-extra-space simulation // that preserves the same algorithmic idea for LeetCode submission. impl Solution { pub fn preorder_traversal(root: OptionRcRefCellTreeNode) - Veci32 { let mut res Vec::new(); let mut stack Vec::new(); if let Some(r) root { stack.push(r); } while let Some(node) stack.pop() { let node_ref node.borrow(); res.push(node_ref.val); if let Some(ref right) node_ref.right { stack.push(right.clone()); } if let Some(ref left) node_ref.left { stack.push(left.clone()); } } res } }Rust 实现说明Morris 遍历需要原地修改树结构而在安全 Rust 的RcRefCellTreeNode模型下不使用unsafe代码无法直接实现指针式线索。因此仓库原文档同样如此处理采用一种「保持同一算法思想、额外空间 O(1)」的栈式模拟版本用于 LeetCode 提交。复杂度分析时间复杂度O(n)。每个节点最多被「找前驱」的过程经过常数次总体仍为线性空间复杂度额外空间 O(1)仅使用常数个指针变量结果数组 O(n)。5. 三种方法对比总结方法是否使用递归是否使用栈时间额外空间特点递归 DFS是否依赖调用栈O(n)O(n)递归栈代码最简洁、最符合直觉树过深时有栈溢出风险迭代 DFS显式栈否是O(n)O(n)栈避免递归栈溢出入栈顺序是关键Morris 遍历否否O(n)O(1)空间最优需临时修改树结构遍历后恢复三者时间均为 O(n)差异集中在额外空间与实现复杂度递归最易写、Morris 最难理解但空间最优。面试中通常先给出递归版本再演进到迭代版本只有被明确追问「能否做到 O(1) 额外空间」时才需要展开 Morris 遍历。6. 常见错误Common Pitfalls6.1 在递归完子节点之后才添加节点值前序遍历要求「先访问当前节点再访问其子节点」。若把res.append(node.val)放到左右子树的递归调用之后得到的就是后序遍历而非前序遍历# Wrong: this is postorder, not preorder preorder(node.left) preorder(node.right) res.append(node.val)判断口诀很简单值记录的位置决定了遍历类型——前序值 → 左 → 右、中序左 → 值 → 右、后序左 → 右 → 值的唯一区别就是这一行代码的位置。6.2 迭代写法中先压入左孩子在栈式迭代方案中必须先压右孩子、后压左孩子。因为栈是 LIFO若先压左孩子左孩子会先被弹出处理导致右子树被提前访问# Wrong: processes right subtree before left stack.append(cur.left) # should push right first stack.append(cur.right)正确的顺序一定是「先 push 右、再 push 左」这样左子树才能保持「先被处理」的前序遍历语义。可对照 python/0144-binary-tree-preorder-traversal.py 中stack.append(cur.right)与cur cur.left的书写顺序来校验自己的实现。6.3 Morris 遍历中忘记移除线索Morris 遍历若在「第二次到达」分支prev.right已指向cur忘记执行prev.right None树结构将残留临时线索导致后续访问逻辑错乱并破坏原树。务必保证每个建立线索的节点在遍历结束前都被恢复。7. 延伸阅读与本仓库相关资源本仓库 articles/README.md 说明了文章撰写规范每篇文章应包含与 NeetCode 视频一致的解法、时间与空间复杂度并尽可能覆盖全部相关解法——本文三种解法正符合这一要求。前序遍历与二叉树的另外两种基本遍历互为姊妹篇建议一并学习以建立完整的遍历体系二叉树中序遍历顺序为「左 → 节点 → 右」在二叉搜索树上输出有序序列同样包含递归、迭代与 Morris 三种解法二叉树后序遍历顺序为「左 → 右 → 节点」常用于自底向上的树形 DP 与删除/释放节点的场景从前序与中序遍历序列构造二叉树前序遍历的第一个元素就是根节点这一性质是「给定两种遍历重建二叉树」类题目的关键仓库中 cpp/0105-construct-binary-tree-from-preorder-and-inorder-traversal.cpp、python/0105-construct-binary-tree-from-preorder-and-inorder-traversal.py 等均有对应实现可作参考。掌握前序遍历后可进一步将其思想迁移到 N 叉树参见 c/0589-n-ary-tree-preorder-traversal.c以及序列化、复制树等需要「先处理父节点」的二叉树问题上。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考