二叉树的认识

二叉树基本性质

1. 每个节点的度最多为2.
2. 度为0的节点比度为2的节点多一个.
   证明：设度为0的节点为n0, 度为1的节点为n1,度为2的节点为n2.
   那么总节点数等于n0+n1+n2,而总边数为0 * n0 + 1 * n1 + 2 * n2.
   而我们知道总边数等于总节点数-1，那么有n0 + n1 + n2 - 1 = n0 * 0 + n1 * 1 + n2 * 2
   即n0 - 1 = n2

遍历

根据根节点被访问的时机，分为前序遍历(根、左子树、右子树)、中序遍历(左子树、根、右子树)、后序遍历(左子树、右子树、根)

特殊二叉树

1、完全二叉树(complete binary tree)
2、满二叉树(full binary tree)-指所有节点的度都是0或2的二叉树(即没有度为1的节点)
3、完美二叉树(perfect binary tree)

关于树结构的理解

节点表示集合(Set),边表示关系(relationship)

学习二叉树的作用

作用一：二叉树是理解高级数据结构的基础

1、完全二叉树-堆、优先队列
2、多叉树/森林-字典树、AC自动机、并查集
3、二叉排序数(BST, Binary Serarch Tree)-AVL树、2-3树、红黑树、B-树、B+树

作用二：二叉树是练习递归技巧的最佳选择

设计/理解递归程序：
(1)数学归纳法-》结构归纳法(k0正确，我们假设ki->k-+1是正确的)=>联立第一和第二步
(2)赋予递归函数一个明确的意义
(3)思考边界问题
(4)实现递归过程

作用三：学习二叉树后，可以使用左孩子右兄弟法来节省空间。

例子：1                 1
    / | \              /
    2 3 4      =>      2
      /\                \
      5 6                3
                        / \
                        5  4
                         \
                          6

三叉树每个节点中存放了三个指针域：左边6个节点->6*3=18个指针域=》有多少个有效指针域：5条边 =>浪费了18 - 5 = 13个指针域
二叉树每个节点中存放了二个指针域：6 * 2 = 12个指针，=》有多少个有效指针域：5条边，5个指针域=》浪费了12 - 5= 7个指针域
可以得到n个节点的k叉树：一个有n*k个指针域，有n-1条边(有效指针域),浪费了n*k - n + 1 = n(k - 1) + 1
=》二叉树浪费n(2 - 1) + 1 => n + 1个指针域

二叉树的基本操作

LeetCode 144.二叉树的前序遍历
LeetCode 589.N叉树的前序遍历
LeetCode 226.翻转二叉树
交换左右子树，再递归翻转左右子树。
LeetCode 剑指Offer 32-II.从上到下打印二叉树II
使用将行号作为参数的递归即可。也可以使用队列 BFS 来进行层序遍历。
LeetCode 107.二叉树的层序遍历II
LeetCode 103.二叉树的锯齿形层序遍历

二叉树的进阶操作

LeetCode 110.平衡二叉树
对获取树高的函数进行修改，在获取树高的函数中对平衡进行判断即可。
LeetCode 112.路径总和
递归向下求值，每次减去当前结点的值，递归结束的条件是遇到叶子结点且刚好求得的值为 0。
LeetCode 105.从前序与中序遍历序列构造二叉树
递归拆分。前序遍历的第一个结点是根结点，在中序遍历中找到该根结点的位置，区分出左右子树，再递归向下拆分左右子树即可。
LeetCode 222.完全二叉树的节点个数
递归数左子树和右子树的结点，加上根结点即可。
LeetCode 剑指 Offer 54. 二叉搜索树的第 k 大结点
方法一：递归判断右子树节点数量和k比较(k <= cnt_R第K大的在右子树，k = cntR + 1第K大的是根节点，k > cnt_R + 1,在左子树中)
方法二：中序遍历二叉搜索树=》有序序列=》返回第K大
LeetCode 剑指 Offer 26. 树的子结构
LeetCode 968. 监控二叉树
LeetCode 662. 二叉树最大宽度