二叉树的主要形式：
1）无数值的二叉树：满二叉树和完全二叉树
2）有数值的二叉树：二叉搜索树和平衡二叉搜索树（AVL树）
平衡二叉搜索树：
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个字数都是一颗平衡二叉树
二叉树的存储方式：
1）链式存储
2）顺序存储–用数组的方式存储二叉树：
设父节点在数组中的下标为i，则左孩子的下标为2i+1，右孩子的下标为2i+2
二叉树遍历方式
二叉树的遍历方式：
1）深度优先（先往深处走，遇到叶子节点再往回走）
① 前序遍历 中左右
实现方法：递归 / 迭代（使用辅助栈）
② 中序遍历 左中右
实现方法：递归 / 迭代（使用辅助栈）
③ 后序遍历 左右中
实现方法：递归 / 迭代（使用辅助栈，前序遍历调换左右并将输出列表翻转）前序遍历和后序遍历的迭代方法可以类推，但中序遍历的迭代方法和前两者不同，需注意
# 三种遍历存在一个统一的方法实现迭代 #下面以中序遍历为例 #先确认遍历顺序，此时为 左中右 helper=[] #定义辅助栈 results=[] #初始化输出列表 helper=[root] #root为根节点 while helper: tmp=helper.pop() if tmp: #按照遍历顺序的反顺序推入栈，注意：中节点后要推入一个空节点到辅助栈中 helper.append(tmp.right) helper.append(tmp) helper.append(None) #在中节点后推入空节点到辅助栈中 helper.append(tmp.left) else: tmp=helper.pop() result.append(tmp.val) return results
前序和中序可以唯一确定一棵二叉树
后序和中序可以唯一确定一棵二叉树
2）广度优先
层次遍历
实现方法：迭代法
层序遍历解决系列问题：右视图 / 层平均值 / N叉树的前序遍历/在每个树行找最大值 / 填充每个节点的下一个右侧节点指针 / 最大深度 / 最小深度
二叉树节点的定义（python版）：
class TreeNode: def __init__(self, value): self.value=value self.left=None self.right=None解题思路
递归三要素：
①确定递归函数的参数和返回值
②确定终止条件
③确定单层逻辑
二叉树的深度与高度
二叉树节点高度：从该节点到叶子节点的最长简单路径上的节点个数 （从底向上，后序）
二叉树节点深度：从根节点到该节点的最长简单路径上的节点个数 （从上到下，先序）
二叉树的最大深度=根节点的高度
二叉树的最小深度是从根节点到最近叶子节点的最短路径上的节点数量
求最小深度和最大深度的差别主要在于处理左右孩子不为空的逻辑
求解方法：递归法（前序/后序）/ 迭代法（层序）
计算完全二叉树的节点数
分两种情况：
1.完全二叉树为满二叉树：节点数=
2
树
深
度
2^{树深度}
2树深度 -1
2.最后一层叶子节点不满：分别递归左右孩子，递归到某深度一定会有左孩子或有孩子是满二叉树
① 如何判断是否是满二叉树：
一直left.left，right.right，并记录递归深度，如果左右深度相同，则为满二叉树② python中的位运算符 > > >> >> < < << <<
< < << << 是左移 末位补0
eg. x<<1是将x的二进制表示左移一位，相当于 x ∗ 2 x*2 x∗2 ; x<<2 相当于 x* 2 2 2^2 22
> > >> >>是右移 相当于➗2
对称二叉树–使用后序遍历思路
解决方案：递归法 fun(left,right) / 迭代法 用辅助队列or辅助栈
统计二叉树的所有路径
从上到下遍历路径 --> 前序遍历(递归/迭代）
所有路径 --> 回溯
二叉搜索树
注意题目中给定条件：是否有重复值，一般情况下没有重复值（严格大于/小于）
迭代法中，一般一起操作两个树都是使用队列模拟类似层序遍历，同时处理两个树节点
完全二叉树一定是平衡二叉树
将二叉搜索树转换为累加树，相当于反中序遍历
代码随想录-二叉树总结篇
