LeetCode | 一文弄懂树：定义、原理、应用与题型分类

在刷 LeetCode 的路上，树（Tree） 是不可绕过的一个知识点。初学时你可能觉得它抽象、难画、难遍历……但其实，树是很“日常”的结构，理解了它的本质，你会发现很多题目都变得清晰了！

这篇文章我们从以下几个方面讲解树👇：

1. 什么是树？（通俗理解）

2. 树的基本原理和结构

3. LeetCode 解题中什么时候用到树？

4. 推荐的 LeetCode 树题训练路径

5. 树的常见类型和题型分类，真题解析

1.什么是树？

树，其实就像是家谱图或文件夹目录结构。

• 一个“根节点”（Root）是家长或根目录

• 每个节点可以有子节点（Children）

• 不能出现环（你不能是你爷爷的爸爸）

举个例子：树结构

C:\
├── Users\
│   ├── Alice\
│   └── Bob\
├── Program Files\
└── Windows\

 2.树的基本原理和术语

• 根节点（Root）：树的最顶部节点

• 叶子节点（Leaf）：没有子节点的节点

• 父节点 / 子节点（Parent/Child）：节点之间的上下级关系

• 高度（Height）：从根到最深叶子的最长路径长度

• 二叉树（Binary Tree）：每个节点最多有两个子节点（左、右）

3. LeetCode 解题中什么时候用到树？

常见应用：

• 表达结构关系（如 DOM 树、组织架构、文件系统）

• 用于搜索 / 分类（如二叉搜索树 BST）

• 递归遍历、分治结构（如前序中序后序）

 #题目参数是 TreeNode 结构

 4.刷题建议：从简单到深入

 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:
            return
        dfs(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]

执行过程：

口诀：一路往左先压栈，弹出访问加答案，然后切换右子树，重复以上直到完。 

总结

       🌳 树
      / | \
  遍历  结构  性质
  / \    |     \
DFS BFS 构造  深度/路径

 只要掌握了递归遍历 + 有序判断 + 构造技巧，就可以轻松应对大部分树题。

我整理了整份资料，刷题卡，想要获得资源，可在VX小程序搜索🔍AI Pulse,发送【leetcode】获取相关资料以及查看AI技术最新内容。

#数据结构 #算法 #树 #Leetcode #刷题技巧