本文对和 二叉树 有关的常见算法基础题思路分类进行分析和总结，并以 Java 为例，适当指出需要注意的编程细节
- 相关题目和代码在 GitHub: https://github.com/brianway/algorithms-learning
- 题目见
com.brianway.learning.algorithms.lectures.binarytree包
判断是否为平衡二叉树
题目见 CheckBalance
思路：
- 判断左子树是否为平衡二叉树，是则返回高度，不是返回 -1
- 判断右子树是否为平衡二叉树，是则返回高度，不是返回 -1
- 若左右子树均时平衡二叉树，则看两者高度差是否大于 1。是则返回 -1，不是则取两者中大的再加上 1
注意：
- 这里对返回值意义复用了，非负数则表示高度，负数表示不是平衡二叉树
判断是否为完全二叉树
题目见 CheckCompletion
思路：
- 使用队列，按层遍历二叉树，分以下几种情况依次判断：
- 如果只有右孩子，返回 false
- 如果已经遍历过最后一个非叶子节点，当前节点还是非叶子节点，返回 false
- 如果左孩子非空，入队
- 如果右孩子非空，入队；如果右孩子空，表示该节点应为最后一个非叶子节点
- 若遍历完，则是完全二叉树
找出搜索二叉树中换位的两个节点
题目见 FindErrorNode
思路：
- 中序遍历二叉树，找到出现降序的节点。第一次出现降序的较大值为换位的两个节点中的较大值，最后一次降序的较小值为换位节点中的较小值
注意：
- 可能出现一次降序，可能出现两次降序。
- 若出现一次降序，则这两个值就是换位节点；
- 若出现两次降序，则第一次降序的较大值和第二次降序的较小值为换位节点
- 可以用非递归方式中序遍历二叉搜索树来实现
打印纸的折痕
题目见 FoldPaper
思路：
- 使用一个队列才存结果
- 每个 fold 里，先递归调用 fold，再将当前折痕方向入队，再递归调用 fold
- 从队列依次取出折痕即可
注意：
- 每个 fold 里的前后两次调用，方向相反，一上一下，和折纸方向有关
二叉树整棵树上节点间最大距离
题目见 LongestDistance
思路：
- 递归的调用 find,每步迭代更新这两个值(当前子树的节点最大距离，到当前子树根结点的最大长度)：(MaxLength,MaxToRoot)，并将其返回
- 当前的 MaxToRoot = max(左子树的 MaxToRoot,右子树的 MaxToRoot) + 1
- 当前的 MaxLength ＝ max(一边的最大距离，两边的最大距离)
- 一边的最大距离 ＝ max(左子树的 MaxLength,右子树的 MaxLength)
- 两边的最大距离 ＝ 左子树的 MaxToRoot + 右子树的 MaxToRoot + 1
注意：
- 需要返回两个值，所以用数组当返回类型
- 分类/划分标准和思路理清了，代码很简单
找到含有节点最多的搜索二叉子树
题目见 MaxSubtree
思路：
- 需要记录满足条件搜索二叉树的最大值，最小值，节点个数，记为数组
info[]，并返回该搜索二叉树的根节点 - 每一步递归对左孩子和右孩子调用，然后分情况讨论
- 左孩子的调用结果是左孩子，右孩子的的调用结果是右孩子，且左右孩子和根节点满足大小关系，更新上述
info[]，返回根节点 - 不满足上面的条件则从左右调用结果中选择节点个数大的结果（题目要求），更新上述
info[]，返回调用结果 - 左右节点个数相等，选择根结点值大的，更新上述
info[]，返回调用结果
- 左孩子的调用结果是左孩子，右孩子的的调用结果是右孩子，且左右孩子和根节点满足大小关系，更新上述
注意：
- 空节点判断，数组初始化(最大值，最小值，个数0)
- 更新
info[]时，尤其对情况一，需要判断左右孩子是否为空的情况
按层打印二叉树并换行
题目见 TreePrinter
思路：
- 使用队列，先将根节点入队
- 使用两个指针 last 和 nlast 分别代表当前行的最后一个节点和下一行的最后一个节点，初始值均为 root
- 每次从队列取出一个节点，并将其左右节点入队，每入队一个，更新 nlast 为入队的节点
- 判断当前取出的节点是否为 last，若是，则说明这时此行最后一个，故更新 last = nlast
注意：
- 每出队一个节点，入队其左右孩子，这里 每次 都需要更新 nlast，因为不知道下一行在何时开始没新节点加入
- 结尾条件需要注意，只有当前节点为 last 且此时队列还非空时，才进行 last 的更新，同时换行，非空这个需要判断，否则会多出一个空行
递归方式实现二叉树的先序、中序和后序的遍历
一定是先左后右，先序、中序和后序指的是根节点遍历的先后
题目见 TreeToSequence
思路：
- 递归调用即可，终止条件是该节点为 null
- 不为 null，则将二叉树的“左”，“根”，“右”按遍历顺序的要求打印
注意：
- 没啥注意的，三四行代码就完了
非递归方式实现二叉树的先序、中序和后序的遍历
题目见 TreeToSequence2
都是使用 栈 来实现的
先序遍历
思路：有点像深度优先遍历
- 使用一个栈，先将根节点压栈，当栈非空时进行以下步骤
- 每次出栈一个节点，并先将其右孩子压栈，再将其左孩子压栈
注意：
- 利用栈“后进先出”的特性，使得右孩子会在左孩子之后出栈
中序遍历
思路：
- 使用栈，先将根节点入栈，当栈非空时进行以下步骤
- 当当前节点和其左孩子均不为空时，将其左孩子入栈，当前节点指向左孩子
- 当当前节点为空或者左孩子为空时，从栈顶取出一个，并将当前节点指向右孩子(可能为空)。若该取出的节点有右孩子，则将右孩子入栈。
注意：
- “当前节点左孩子为空则出栈”用于触发左子树到顶的情况
- “当前节点为空则出栈”用于触发右孩子为空的回退
后序遍历
思路：核心在于使用最近访问节点 last 来标记是从左孩子还是右孩子遍历完返回的，从而确定是入栈还是出栈
- 使用栈，先将根节点入栈，当栈非空时进行以下步骤
- 每次查看栈顶节点(但不出栈)，根据栈顶节点的情况分类判断：
- 左孩子非空且上次访问既不为左孩子也不为右孩子，则左孩子入栈
- 否则，若右孩子非空且上次访问不为右孩子，则右孩子入栈
- 否则，表示此时左右孩子均为空或均访问过，栈顶出栈，并记为最近访问节点 last
注意：
- 按上面的逻辑左孩子出栈后，右孩子才会入栈，所以是先左后右的顺序
- 右孩子是上次访问的节点时，前两条都不满足，所以一定会是孩子的根结点出栈
