二叉树分类
没有数值 | 满⼆叉树 | 如果⼀棵⼆叉树只有度为0的结点和度为2的结点，并且度为0的结点在同⼀层 上，则这棵⼆叉树为满⼆叉树 满⼆叉树，也可以说深度为k，有2^k-1个节点的⼆叉树 |
|
没有数值 | 完全⼆叉树 | 在完全⼆叉树中，除了最底层节点可能没填满外，其余每层节点数 都达到最⼤值，并且最下⾯⼀层的节点都集中在该层最左边的若⼲位置。 若最底层为第 h 层，则该层包含 1~ 2^h -1 个节点 |
|
有数值 | ⼆叉搜索树 (有序树) | 若它的左⼦树不空，则左⼦树上所有结点的值均⼩于它的根结点的值； 若它的右⼦树不空，则右⼦树上所有结点的值均⼤于它的根结点的值； 它的左、右⼦树也分别为⼆叉排序树 |
|
有数值 | 平衡⼆叉搜索树 也称: AVL | 它是 ⼀棵空树或它的左右两个⼦树的⾼度差的绝对值不超过1，并且左右两个⼦树都是⼀棵平衡 ⼆叉树 |
|
二叉树存储
⼆叉树可以链式存储(即，指针)，也可以顺序存储(即，数组)
链式存储 | 是通过指针把分布在散落在各个地址的节点串联⼀起 ⽤链式表⽰的⼆叉树，更有利于我们理解，所以⼀般我们都是⽤链式存储⼆叉树。
|
顺序存储 | 元素在内存是连续分布的 如果⽗节点的数组下表是i，那左节点: i * 2 + 1，右节点: i * 2 + 2
|
二叉树的遍历
⼆叉树主要有两种遍历⽅式：【深度】 + 【广度】
(往下走,然后往回走) | 前序遍历（递归法，迭代法） 根左右 中序遍历（递归法，迭代法） 左根右 后序遍历（递归法，迭代法） 左右根 一般使用栈(先进后出·) |
(一层一层遍历完再往下走) | 层次遍历（迭代法） 一般使用队列实现(FIFO, 先进先出) |
二叉树的定义
二叉树的链式定义
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
⼆叉树的递归遍历
递归三要素: 1. 确定参数和返回值 2. 确定终止条件 3. 确定递归逻辑
学习参考
https://programmercarl.com
标签：结点,遍历,递归,理论,LeeCode,二叉树,链式,节点 From： https://blog.51cto.com/u_13682316/6065481