字典树，即 Trie 树，又称单词查找树或键树，是一种树行的结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计
优点：最大限度的减少无谓的字符串比较，查询效率比哈希表高
Trie 树的核心思想是空间换时间
利用字符串的公共前缀来降低查询时间的开销已达到提高效率的目的
- 节点本身不存完整单词
- 从根节点到某一节点，路径上经过的字符连接起来，为改节点的字符串
- 每个节点的所有子节点路径代表的字符都不相同
红黑树是 近似平衡 的二叉搜索树（Binary Search Tree），它能确保任何一个结点的左右子树的 高度差小于两倍。具体来说，黑红树是满足以下条件的二叉搜索树：
- 每个结点要么是红色，要么是黑色
- 根节点是黑色
- 每个叶结点（NIL 结点，空节点）是黑色
- 不能有相邻的两个红色结点
- 从任一结点到其每个叶子的所有路径都包含相同数目的黑色节点
-
class Solution: def climbStairs(self, n: int) -> int: if n <= 2: return n f1, f2, f3 = 1, 2, 0 for n in range(2, n): f3 = f1 + f2 f1, f2 = f2, f1 + f2 return f3
-
class Solution: def generateParenthesis(self, n: int) -> List[str]: ans = [] def _generate(left, right, s): if left == n and right == n: ans.append(s) return if left < n: _generate(left + 1, right, s + '(') if right < left: _generate(left, right + 1, s + ')') _generate(0, 0, '') return ans