笺札

二叉搜索树的插入操作 🎯 问题描述（来源于LeetCode） 描述： 给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。 注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。 说明： 树中的节点数将在 [0, 104]的范围内。 -108 <= Node.val <= 108 所有值 Node.val 是 独一无二 的。 -108 <= val <= 108 保证 val 在原始BST中不存在。 示例： 示例 1： 12输入：root = [4,2,7,1,3], val = 5输出：[4,2,7,1,3,5] 示例 2： 12输入：root = [40,20,60,10,30,50,70], val = 25输出：[40,20,60,10,30,50,70,null,null,25] 💻 解题思路 思路1：递归 思路1：代码实现 12345...

二叉搜索树中的搜索 🎯 问题描述（来源于LeetCode） 描述： 给定二叉搜索树（BST）的根节点 root 和一个整数值 val。 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。 说明： 树中节点数在 [1, 5000] 范围内 1 <= Node.val <= 107 root 是二叉搜索树 1 <= val <= 107 示例： 示例 1： 12输入：root = [4,2,7,1,3], val = 5输出：[] 示例 2： 12输入：root = [4,2,7,1,3], val = 2输出：[2,1,3] 💻 解题思路 思路1：递归 思路1：代码实现 1234567891011121314# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val...

从前序与中序遍历序列构造二叉树 🎯 问题描述（来源于LeetCode） 描述： 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。 说明： 1 <= preorder.length <= 3000 inorder.length == preorder.length -3000 <= preorder[i], inorder[i] <= 3000 preorder 和 inorder 均 无重复 元素 inorder 均出现在 preorder preorder 保证 为二叉树的前序遍历序列 inorder 保证 为二叉树的中序遍历序列 示例： 示例 1： 12输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]输出: [3,9,20,null,null,15,7] 示例 2： 12输入: preorder = [-1], inorder = [-1]输出: [-1] ...

从中序与后序遍历序列构造二叉树 🎯 问题描述（来源于LeetCode） 描述： 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。 说明： 1 <= inorder.length <= 3000 postorder.length == inorder.length -3000 <= inorder[i], postorder[i] <= 3000 inorder 和 postorder 都由 不同 的值组成 postorder 中每一个值都在 inorder 中 inorder 保证是树的中序遍历 postorder 保证是树的后序遍历 示例： 示例 1： 12输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]输出：[3,9,20,null,null,15,7] 示例 2： 12输入：inorder = [-1], postorde...

字典树 基本概念 字典树（Trie），又称前缀树或单词查找树，是一种用于高效存储和检索字符串集合中键值的数据结构。它的每个节点代表一个字符，从根节点到某个节点路径上的字符组成一个字符串。字典树广泛应用于字符串前缀匹配、自动补全、单词计数等场景，能够在 O(L) 时间内完成插入、查找和前缀查询（L 为字符串长度） 数据结构的三要素 逻辑结构：树形结构，每个节点包含若干指向子节点的指针（通常用字典或数组实现），根节点为空字符，每个节点可以标记是否为一个单词的结尾。 存储结构： 链式存储：每个节点维护一个字典（如 Python 的 dict）或固定大小的数组（如 26 个字母），存储指向子节点的引用。 字典实现适用于字符集较大的场景（如 Unicode），数组实现适用于小字符集（如英文小写字母），访问速度更快但空间固定。 数据的运算： 插入：从根节点开始，依次将字符串的每个字符作为键创建子节点，最后标记节点为单词结尾。 查找：沿着字符路径遍历，若路径存在且最终节点被标记为单词结尾，则查找成功。 前缀查询：给定前缀，检查是否存在以该前缀开头的单词，只需路径存在即可（无需结...

中序遍历：递归+非递归实现 基本概念 中序遍历（Inorder Traversal） 是二叉树深度优先遍历（DFS）的一种。其访问顺序为：左子树 → 根结点 → 右子树。 对于二叉搜索树（BST），中序遍历的结果是升序序列。 递归实现直观，非递归实现需借助栈模拟系统调用过程。 算法步骤 递归版： 若当前结点为空，直接返回。 递归遍历左子树。 访问当前结点（如记录值）。 递归遍历右子树。 非递归版（栈）： 初始化空栈，cur 指向根结点。 循环直到 cur 为空且栈为空： 将 cur 及其所有左孩子依次压栈（cur = cur.left）。 弹出栈顶结点，访问它。 将 cur 设为弹出结点的右孩子，继续循环。 内部实现 12345678910111213141516171819202122232425262728293031323334353637from typing import List, Optionalclass TreeNode: def __init__(self, val=0, left=None, right=None): ...

特殊二叉树：斜树 / 满二叉树 / 完全二叉树 1. 斜树（Skewed Tree） 定义：所有结点都只有左孩子（左斜树）或只有右孩子（右斜树）。 特点：退化为线性结构，树的高度等于结点数。 性能：查找、插入、删除退化为 O(n)O(n)O(n)，失去了二叉树的优势。 2. 满二叉树（Full Binary Tree / Perfect Binary Tree） 定义：所有分支结点都有左孩子和右孩子，且所有叶子都在同一层。 性质（高度为 hhh，根为第 1 层）： 第 iii 层结点数：2i−12^{i-1}2i−1 总结点数：2h−12^h - 12h−1 叶子数：2h−12^{h-1}2h−1 特点：形态完美，所有叶子深度相同。 3. 完全二叉树（Complete Binary Tree） 定义：对高度为 hhh、有 nnn 个结点的二叉树，当且仅当其每个结点都与高度为 hhh 的满二叉树中编号 1 到 nnn 的结点一一对应时，称为完全二叉树。 通俗理解：除最后一层外，其余层结点数达到最大；最后一层结点向左靠拢。 性质： 叶子结点只可能在最后两层出...

树的分类 根据不同的划分标准，树可以分为多种类型： 1. 按结点有序性 有序树：树中结点的各子树从左到右是有顺序的，不能互换。 无序树：结点的各子树之间没有顺序关系。 2. 按度数限制 一般树：结点的度不受限制（通常 mmm 叉树即每个结点最多 mmm 个孩子）。 二叉树：每个结点最多两个孩子（0,1,20,1,20,1,2），且区分左、右子树。 mmm 叉树：每个结点最多 mmm 个孩子。 3. 按节点值 有序树（如二叉搜索树）：左子树所有结点值小于根，右子树所有结点值大于根。 堆：大顶堆（根 ≥ 孩子）、小顶堆（根 ≤ 孩子）。 4. 按形态（特殊二叉树） 斜树：所有结点只有左孩子（左斜树）或只有右孩子（右斜树）。 满二叉树：所有分支结点都有左、右子树，且所有叶子都在同一层。 完全二叉树：除最后一层外，其余层结点数达到最大，最后一层结点向左靠拢。 5. 按平衡性 平衡二叉树：任意结点左右子树高度差 ≤ 1（如 AVL 树）。 非平衡二叉树：不满足平衡条件。 6. 按实际应用 二叉搜索树（BST）：快速查找、插入、删除。 堆（Heap）：优先...

树的定义与基本术语 树的定义 树（Tree） 是 nnn（n≥0n \ge 0n≥0）个结点的有限集合。当 n=0n = 0n=0 时称为空树。在任意一棵非空树中： 有且仅有一个特定的结点称为根（Root）。 当 n>1n > 1n>1 时，其余结点可分为 mmm（m>0m > 0m>0）个互不相交的有限集 T1,T2,…,TmT_1, T_2, \dots, T_mT1​,T2​,…,Tm​，其中每一个集合本身又是一棵树，并且称为根的子树（Subtree）。 基本术语 术语 英文 解释 结点 Node 树中的基本元素，包含数据项和指向子树的指针。 度 Degree 结点拥有的子树个数。树的度是树内各结点度的最大值。 叶子（终端结点） Leaf 度为 0 的结点。 分支结点（非终端结点） Branch Node 度大于 0 的结点。 孩子 Child 结点子树的根称为该结点的孩子。 双亲 Parent 该结点称为其孩子的双亲（父结点）。 兄弟 Sibling 同一双亲的孩子之间互称兄弟。 祖先...

树的存储结构 树的存储结构主要分为三种：双亲表示法、孩子表示法、孩子兄弟表示法。 1. 双亲表示法 实现：用一组连续空间存储结点，每个结点附加一个指针（下标）指向其双亲。 优点：容易找到双亲。 缺点：找孩子需要遍历。 12345678typedef struct { ElemType data; int parent; // 双亲位置下标（-1 表示根）} PTNode;typedef struct { PTNode nodes[MAX_SIZE]; int n; // 结点数} PTree; 2. 孩子表示法 实现：用数组存储结点，每个结点维护一个链表，链接其所有孩子。 优点：容易找到孩子。 缺点：找双亲需要遍历。 123456789typedef struct ChildNode { int child; // 孩子下标 struct ChildNode *next;} ChildNode;typedef ...