LeetCode | 一文弄懂树：定义、原理、应用与题型分类
在刷 LeetCode 的路上，树（Tree） 是不可绕过的一个知识点。初学时你可能觉得它抽象、难画、难遍历……但其实，树是很“日常”的结构，理解了它的本质，你会发现很多题目都变得清晰了！
这篇文章我们从以下几个方面讲解树👇：
-
什么是树？（通俗理解）
-
树的基本原理和结构
-
LeetCode 解题中什么时候用到树？
-
推荐的 LeetCode 树题训练路径
-
树的常见类型和题型分类，真题解析
1.什么是树？
树，其实就像是家谱图或文件夹目录结构。
-
一个“根节点”（Root）是家长或根目录
-
每个节点可以有子节点（Children）
-
不能出现环（你不能是你爷爷的爸爸）
举个例子：树结构
C:\
├── Users\
│ ├── Alice\
│ └── Bob\
├── Program Files\
└── Windows\
2.树的基本原理和术语
-
根节点（Root）：树的最顶部节点
-
叶子节点（Leaf）：没有子节点的节点
-
父节点 / 子节点（Parent/Child）：节点之间的上下级关系
-
高度（Height）：从根到最深叶子的最长路径长度
-
二叉树（Binary Tree）：每个节点最多有两个子节点（左、右）
3. LeetCode 解题中什么时候用到树？
常见应用：
-
表达结构关系（如 DOM 树、组织架构、文件系统）
-
用于搜索 / 分类（如二叉搜索树 BST）
-
递归遍历、分治结构（如前序中序后序）
#题目参数是 TreeNode 结构
4.刷题建议：从简单到深入
| 难度 | 题目说明 |
|---|---|
| 简单 | 94, 104, 100, 101, 110, 112 |
| 中等 | 102, 105, 235, 572 |
| 困难 | 124（最大路径和）、297（序列化树） |
5.树的常见类型和题型分类，真题解析
5.1.遍历类题目（DFS/BFS）
-
前序 / 中序 / 后序遍历（递归 or 迭代）
-
层序遍历（BFS）
【LeetCode 94】二叉树中序遍历(Binary Tree Inorder Traversal)
给定一棵二叉树的根节点，返回它的中序遍历结果（按中序顺序排列的所有节点值组成的列表）。
中序遍历（Inorder）顺序是：左 → 根 → 右
# 方法1：递归法def inorderTtaversal(root):res=[]def dfs(node):if not node:returndfs(node.left) # 先左子树res.append(node.val) # 再根节点dfs(node.right) # 最后右子树dfs(root)return res#时间复杂度：O(n)#空间复杂度：O(n)（递归栈）# 方法2：迭代法（栈实现，面试更推荐）最优解
#核心思路：使用一个 stack（栈）模拟递归中的函数调用过程，显式地控制回溯。
def inorderTraversal(root):res,stack=[],[] # res 是结果数组，stack 是辅助栈curr=root # curr 是当前访问的节点while curr or stack: #只要还有没处理完的节点（curr 非空），或者栈里还有未访问的“根节点”，就继续遍历。while curr :stack.append(curr) # 把当前节点入栈curr=curr.left # 一直往左子树走curr=stack.pop() # 左子树走到底后弹出栈顶res.append(curr.val) # 访问当前节点，加入结果数组curr=curr.right # 准备访问右子树return res#时间复杂度：O(n)
#空间复杂度：O(n)（显式栈）#方法3：Morris 遍历（空间 O(1)）
#这是进阶技巧，不使用递归或栈，通过修改树结构临时建立“线程”，空间复杂度为 O(1)。了解即可，极少用于面试。例如：给定二叉树(迭代法)
1\2/3
中序结果应为 [1,3,2]
执行过程：
| 操作 | 栈内容 | 当前节点 curr | 输出 res |
|---|---|---|---|
| 入栈 1 | [1] | 1 → 左(None) | [] |
| 弹出 1 | [] | 1 → 右(2) | [1] |
| 入栈 2 | [2] | 2 → 左(3) | [1] |
| 入栈 3 | [2, 3] | 3 → 左(None) | [1] |
| 弹出 3 | [2] | 3 → 无右 | [1, 3] |
| 弹出 2 | [] | 2 → 无右 | [1, 3, 2] |
口诀：一路往左先压栈，弹出访问加答案，然后切换右子树，重复以上直到完。
| 解法 | 是否推荐 | 特点 |
|---|---|---|
| 递归法 | ✅ 初学者优先 | 简单好写 |
| 迭代法 | ✅✅ 面试最推荐 | 清晰、无递归栈限制 |
| Morris | ❌ 面试不推荐 | 改结构、难写、易出 bug |
总结
🌳 树/ | \遍历 结构 性质/ \ | \
DFS BFS 构造 深度/路径
只要掌握了递归遍历 + 有序判断 + 构造技巧，就可以轻松应对大部分树题。
我整理了整份资料，刷题卡，想要获得资源，可在VX小程序搜索🔍AI Pulse,发送【leetcode】获取相关资料以及查看AI技术最新内容。
#数据结构 #算法 #树 #Leetcode #刷题技巧