代码随想录 二叉树：二叉树总结
二叉树理论基础
二叉树的种类
满二叉树、完全二叉树、二叉搜索树、平衡二叉搜索树
满二叉树有一个性质，高度为k的满二叉树，节点数量为
二叉搜索树的中序遍历是一个有序数组，这个性质可以用来构造、验证和累加。
平衡二叉树的关键是找到中间节点（平衡节点），尽量平衡得构造其左右子树
二叉树的存储
一般用链表存储。对于一个完美二叉树，按照层序遍历也可以存储为数组，则每个节点都对应数组唯一的索引。后面题目暂时没用到这个性质。
二叉树遍历方式
- 深搜
- 前中后序遍历
- 前中后迭代法，使用栈模拟，其中中序遍历和前后序遍历实现不同
- 前中后序统一迭代法，利用 nullptr 标记或者使用 boolean 标记
- 广搜
- 层序遍历，通过队列模拟
二叉树的属性
翻转二叉树
- 对每个子树进行翻转，即对每个节点做左右子节点的交换。
对称二叉树
- 递归：后序，因为一个树是否对称取决于：1、左右子树根节点2、左子树的左子树和右子树的右子树对称3、左子树的右子树和右子树的左子树对称。
- 迭代：
二叉树最大深度
- 递归：后序。树的最大深度等同于树的高度/根节点的最大高度。可以使用后序遍历求树高度，因为任意一棵树的最大高度取决于左右节点的最大高度
二叉树最小深度
- 递归：树的最小深度等同于根节点的最小高度。可以使用后序遍历，因为任意一颗树的最小高度取决于左右节点的最小高度的最小值
完全二叉树节点个数
- 递归：利用满二叉树节点个数的性质，从完全二叉树中拆出满二叉树简化计算。使用后序遍历，因为一棵树的节点数量取决于左右子树的节点数量 或者 如果是满二叉树就不用求左右子树节点数量直接使用公式即可。
- 迭代：层序遍历，result++就行
平衡二叉树
- 递归：后序。平衡意味着每个节点都应该满足其左右子树的高度相差不超过1。而节点的高度取决于左右两子节点的高度，所以应该采用后序遍历。
- 迭代：不推荐
二叉树所有路径
- 递归：一条路径上根节点应该在左右子节点的左边，因此前序遍历。另外首次涉及到回溯，全局的path跟着节点走。可以选择递归后将节点加入path也可以进入递归前将节点加入path，两者均可
左叶子之和
- 递归：一棵树的左叶子之和等于左子树左叶子之和加右子树左叶子之和，因此使用后序遍历。但是需要注意两种特殊情况：遍历节点为叶子节点、遍历节点的左子树是叶子节点。
左下角的值
- 迭代：层序遍历不断记录每层的最左边的值
- 递归：前中后序都可以，因为没有中处理逻辑，保证左在右前面即可。先不断向左递归，遇到叶子节点即到该路径最大深度，更新最大深度和最大深度节点值。然后返回/回溯，向右方向递归。
路径总和
- 递归：设置一个count跟随节点，记录遍历到该节点时的路径和，使用前序遍历。因为要求找到合适的路径即可返回，不必搜索所有的路径，所以将递归嵌套进判断中。
二叉树的修改和构造
- 翻转二叉树
- 递归：前序，交换左右孩子
- 构造二叉树
- 递归：前序，给定中序遍历和后序遍历构造二叉树，将后序遍历的最后一个元素作为分割点分割中序数组，随后使用中序左数组确定后序左数组。使用中序左数组和中序右数组，后序左数组和后序右数组，分别递归处理左区间和右区间。推荐使用左闭右开区间。
- 构造最大二叉树
- 递归：前序，以数组最大值构造节点并分割数组，以左右数组构造左右子树。
- 合并两个二叉树
- 递归：前序。在其中一颗树原地构造。同时遍历两棵树的节点，考虑好几种情况：节点1空、节点2空、节点1和节点2不为空。
二叉搜索树属性
- 二叉搜索树中的搜索
- 递归：按照一定的方向搜索，有几种情况：空节点、目标节点、比目标节点大、比目标节点小。对于前两种情况，应该直接返回遍历节点。对以后两种，应该进入递归。
- 验证二叉搜索树
- 递归：中序，二叉搜索树是一个有序数组。左中右。左：先验证左子树是否为有效BST。中：就是检查当前节点值是否大于之前遍历过的最大值，如果是，更新 maxVal，如果不是，说明不是有效BST，直接返回false。右：验证右子树是否为有效BST。左子树、当前节点验证、右子树都通过，才返回true
- 递归：后序。当前遍历节点是二叉树有三个条件：左子树是BST，右子树是BST，当前节点值大于左子树最大值，小于右子树最小值。因为除了需要知道子树是否是二叉搜索树还需要知道最大值和最小值，因此将bool和最小值最大值封装成一个结构体作为返回值。
- 二叉搜索树的最小绝对差
- 递归：中序。双指针计算相邻两节点差值，不断更新保持最小。
- 二叉搜索树的众数
- 递归：中序。双指针，记录当前节点值出现的次数，与前一个结点相同+1，新节点值则置1。判断次数与最大次数，然后按照要求更新结果集（直接加入或清空后再加入）。
- 二叉搜索树转为累加树
- 递归：中序。双指针，右中左。
二叉树公共祖先问题
- 二叉树的公共祖先
- 递归：后序。某节点是否是给定节点的公共祖先取决于其左右节点是否是给定节点的祖先情况。
- 二叉搜索树的公共祖先
- 递归：因为二叉搜索树有顺序，因此某节点是否是给定节点的最近公共祖先就不用获取左右节点的信息了，而是根据判断只获取一边即可。这也是搜索某条边与搜索整个树的写法区别。
二叉搜索树的修改与构造
- 二叉搜索树中的插入操作
- 递归：遍历顺序无所谓，遇到空节点后构造并返回即可。
- 二叉搜索树中的删除操作
- 递归：前序。理清楚要删除的节点情况。
- 修剪二叉搜索树
- 递归：前序。修剪后的树如果左右子树都需要修剪就取决于修剪后的左右子树。另外若不在区间，直接剪其中一个子树。
- 构造二叉搜索树
- 递归：前序，使用数组中间节点分割。使用分割后的数组构造左右子树