力扣总结 数据结构（六）：树

树是一种非线性的数据结构，本质是节点的有限集。其定义是递归的：

• 有且仅有一个特定的称为根（root）的节点
• 当节点数量 > 1 时，其余节点可分为若干个互不相交的有限集，其中每个集合也可以看作一颗树，称之为根的子树。

从图的观点来看，树也可视为一个拥有 N 个节点和 N-1 条边的一个有向无环图。

树的应用非常广泛，也常和其它数据结构和算法有联系，尤其是递归。

1 基础

1.1 遍历

• 0094 二叉树的中序遍历
• 0103 二叉树的锯齿形层序遍历
• 0144 二叉树的前序遍历
• 0145 二叉树的后序遍历
• 0872 叶子相似的树

1.2 递归

• 0101 对称二叉树
• 0226 翻转二叉树
• 0508 出现次数最多的子树元素和
• 0606 根据二叉树创建字符串
• 0671 二叉树中第二小的节点
• 0814 二叉树剪枝

2 进阶

2.1 遍历

• 0112 路径总和
• 0113 路径总和 II
• 0116 填充每个节点的下一个右侧节点指针
• 0117 填充每个节点的下一个右侧节点指针 II
• 0655 输出二叉树
• 0662 二叉树最大宽度

2.2 递归

• 0106 从中序与后序遍历序列构造二叉树
• 0110 平衡二叉树
• 0124 二叉树中的最大路径和
• 0236 二叉树的最近公共祖先
• 0337 打家劫舍 III

3 挑战

• 0834 树中距离之和
• 0889 根据前序和后序遍历构造二叉树

*4 二叉搜索树

4.1 基础

• 0098 验证二叉搜索树
• 0108 将有序数组转换为二叉搜索树
• 0173 二叉搜索树迭代器
• 0235 二叉搜索树的最近公共祖先
• 0669 修剪二叉搜索树
• 0701 二叉搜索树中的插入操作

4.2 进阶

• 0096 不同的二叉搜索树
• 0095 不同的二叉搜索树 II
• 0450 删除二叉搜索树中的节点
• 0501 二叉搜索树中的众数
• 0530 二叉搜索树的最小绝对差
• 0538 把二叉搜索树转换为累加树

4.3 挑战

• 0099 恢复二叉搜索树

*5 树哈希

• 0297 二叉树的序列化与反序列化
• 0449 序列化和反序列化二叉搜索树
• 0572 另一个树的子树
• 0652 寻找重复的子树