二叉树

二叉树结点的定义

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};  //分号记得

有关二叉树的一些概念

1. 根节点：位于二叉树顶层的节点，没有父节点。
2. 叶节点：没有子节点，两个左右子节点的指针为空。
3. 节点的层：从顶到底递增，根节点所在层为1；
4. 节点的度：节点的子节点的数量。二叉树中，度的范围是0,1,2。
5. 边：连接两个节点的线段。即节点指针。
6. 二叉树的高度：从根节点到最远叶节点所经过的边的数量。
7. 节点的深度：从根节点到该节点所经过的边的数量。
8. 节点的高度：从最远叶节点到该节点所经过的边的数量。

二叉树的类型

1. 完美二叉树(满二叉树)：每一层都填满了节点，并且最底层节点的度为0，其余所有层的度为2，这个填满指的是节点都有左右子节点。如果树的高度为h（节点计数），则节点总数为2^(h)-1。典型的细胞分裂现象。
2. 完全二叉树：除了最底层节点没有被填满外，其他所有层节点被填满。且最底层节点靠左填充。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。
3. 完满二叉树：除了叶子结点外，其余所有节点都有两个子节点。
4. 平衡二叉树：任意节点的左子树和右子树的高度差的绝对值不超过1。
5. 二叉搜索树：它是一个有序树，若左子树不为空，则左子树上所有节点的值小于根节点的值。若右子树不为空，则右子树上所有节点的值大于根节点的值。并且它的左右子树也分别为二叉搜索树。
6. 平衡二叉搜索树：又被称为AVL(Adelson-Velsky and Landis)树，平衡二叉树和二叉搜索树的结合体。
7. 满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。