简介
数据结构与算法这一分类的文章，将采用严蔚敏《数据结构与算法》一书的顺序结合leetcode题目Go实现，实践与理论相结合的方式记录学习过程。
基础
- 节点拥有的子树数为节点的度，度为0的节点为叶子节点
- 节点的层次由根开始，根为第一层。节点的最大层次为树的深度或高度
- 森林是若干不相交互的树集合
- 二叉树的第i层，至多有2的i-1次方个节点。深度为k的二叉树，至多有2的k次方-1个节点
- 对于任意二叉树，度为2的节点树为n2，则叶子节点树n = n2 + 1
- 深度为k且有2的k次方-1个节点的二叉树为满二叉树，完全二叉树为当且仅当每一个节点与满二叉树中编号节点一一对应时
- 具有n个节点的完全二叉树的深度为log2(n)+1
二叉树常见问题
- 二叉树的遍历，先序遍历，中序遍历，后序遍历
- 解决二叉树问题的一个重要思想就是递归，大体套路可以先考虑当前根局部解决的情况，然后递归操作以子节点为根的子树
- 二叉搜索树
- 树的变形
- 深度优先搜索，广度优先搜索
- 二叉平衡树
递归
- 617 合并两个二叉树，节点重合的求和。递归思想解决就是，当前根节点重合的求和。左节点的合并两个树的左节点，右节点的合并两个树的右节点，最后考虑边界条件
- 965 判断二叉树的所有节点数值是否一样，递归判断根节点与左右节点的值是否相同，如果左右节点为空，则不用比较
- 872 比较两个树的叶子节点值序列是否相同。可以通过递归操作，收集每个树左右子树的叶子节点值，先左后右。最后比较
- 104 求二叉树的深度。右子树的深度与左子树深度的较大值+1
- 226 翻转二叉树，根节点的左子树等于翻转之后的右子树，根节点的右子树等于翻转之后的左子树
二叉搜索树
- 二叉搜索树 左子节点 < 根节点 <= 右子节点或者左子节点 <= 根节点 < 右子节点
- 700 搜索节点=给定的值
- 669 给定最小最大值，修剪二叉搜索树。思路：修剪当前树，直到当前树根节点落在范围内，递归修剪左子树和右子树
- 108 有序数组构建二叉搜索树。数组中间树作为当前根节点，左边部分作为左子树的节点，右边作为右子树节点，递归填充
- 783 求二叉搜索树相近节点之间最小差值，中序遍历
- 530 求二叉搜索树节点之间最小差值，中序遍历
树的变形
- 897 把二叉搜索树变成单向递增，每个节点只有一个右子节点。总体思路，先两边后中间，把右子树变为每个节点只有一个右子节点，把左子树变为每个节点只有左子节点，最后调整为最左子节点为当前树的根节点。递归操作
深度优先搜索，广度优先搜索
- 深度优先使用栈，广度优先用队列
- 637 计算二叉树每一层节点。广度优先，累加当前层数值，记录当前层平均值。记录下一层入队节点的个数。