前言
今天是算法训练营的第十三天，不得不说由于第十一天的题目思维含量有点高，导致文档一直没写的出来从而拖着后面的文档也没及时写，希望后面不要再发生这种情况。
今天是二叉树开头，题目主要围绕二叉树的几种遍历方式展开，总体来说难度不算特别高，虽然题量相对之前来说比较大，但是猛猛AC的感觉超爽。
理论基础
二叉树的理论基础，说实话之前数据结构课程期间学习的二叉树内容由于太久没看基本上忘得差不多了，这是个回顾知识的好机会。
二叉树种类
解题过程中的二叉树主要有两种形式：满二叉树和完全二叉树。
满二叉树
首先是满二叉树，满二叉树是指一个二叉树只有度为0或者度为2的节点，并且度为0的节点在同一层上。
假设一颗
满二叉树的深度为k，那么这颗二叉树的节点数为2^k – 1
下图为一颗满二叉树：
完全二叉树
在完全二叉树中，除了最底层节点没填满外（有额外条件！！），其余每层都达到节点数最大值，并且最下面一层的节点都集中在最左边若干位置（简单说就是在层序遍历的时候最后一层不会跳一个标数字，每个节点的序号都能和满二叉树时的序号对应上）。
假设一个完全二叉树的最底层为h层，则该层包含1~2^(h – 1)个节点
以下是一个完全二叉树的典型判断例子：
二叉搜索树
二叉搜索树与前面的两个二叉树相比，最大区别就是二叉搜索树携带数值，并且二叉搜索树是有序树。
有序树：二叉树中的有序树是指树中任意节点的子节点从左到右有确定的顺序，不可随意交换，本质上二叉树因其独特的左、右子树之分，被视为一类严格的有序树。二叉树中不存在度大于2的节点，且左右子树顺序不可颠倒，任何节点在缺失一侧子树时，都能明确其位置。
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树
左小右大
下面是两棵搜索树例子：
平衡二叉搜索树
平衡二叉搜索树又称AVL树（具体全称懒得记了），具有以下性质：它是一棵空树或它左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。（这边解释的有点抽象，简单说就是既是二叉搜索树，又是平衡二叉树）
下图为平衡二叉树示例：
最后一棵不是平衡二叉树，因为左右子树高度差绝对值超过1。
二叉树的存储方式
二叉树的存储方式主要有链式存储和顺序存储。
链式存储使用指针，顺序存储使用数组。
链式存储的实现主要是使用指针把分布在各个地址的节点给串联起来，非常常见，应该说两种存储方式都挺常见的。
链式存储如图（看到左右指针应该会觉得这下看懂了）：
再看顺序存储，顺序存储是用数组来存储，存储方式大致吻合层序遍历：
如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。
但是用链式表示的二叉树，更有利于我们理解，所以一般我们都是用链式存储二叉树。
二叉树的遍历方式
在先前的学习过程中，我对二叉树的遍历基本脑子里没有知识框架，只知道有递归法遍历以及前中后序遍历及层序遍历，这边再次进行一次巩固了。
二叉树的主要遍历方式有两种：
1.深度优先遍历DFS：先往深走，只要还有深就一直往下走，走到叶子节点再回头
2.广度优先遍历BFS：把每一次遍历完了再去下一层（层序遍历）
在上面两种遍历方式的基础上再向下扩展一步：
- 深度优先遍历DFS：
- 前序遍历（递归法、迭代法）
- 中序遍历（递归法、迭代法）
- 后续遍历（递归法、迭代法）
- 广度优先遍历BFS：
- 层序遍历（迭代法）
此处的前中后指的是中间节点在什么时候遍历：
- 前序遍历：中左右
- 中序遍历：左中右
- 后序遍历：左右中
二叉树的定义
主要展示链式存储的二叉树节点定义方法
class TreeNode:
def __init__(self, val, left = None, right = None):
self.val = val
self.left = left
self.right = right二叉树的递归遍历
虽然说二叉树和递归脱不开关系，而且使用递归来遍历二叉树相较于迭代法写法也更加简单，但我个人而言更加倾向于使用迭代法来实现，主要原因可能是因为对递归的理解深度还不够加上一些厌恶递归的滤镜。
递归算法具有方法论，每次写递归都要确定以下三个要素，可以提高递归正确性：
- 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
- 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
- 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
下面以前序遍历作为例子，模拟方法论的思考过程（写的伪代码）：
第一步：确定递归函数的参数和返回值：
这一步在python里就那啥多了，因为python中是先定义一个数组最后再输出数组的
res = []return res第二步：确定终止条件：
这边是走到叶子节点就回头，符合深度优先遍历：
def dfs(node): if node is None: return第三步：确定单层递归的逻辑：
由于是前序遍历，所以是先处理中间节点，再处理左节点，最后处理右节点。
res.append(node.val) #先处理中间节点
dfs(node.left) #再处理左节点
dfs(node.right) #最后处理右节点将以上内容整合，可得到具体实现代码如下：
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def dfs(node):
if node is None:
return
res.append(node.val)
dfs(node.left)
dfs(node.left)
dfs(root)
return res有了前序遍历后再实现中序遍历和后续遍历理解起来就比较简单了。
中序遍历：
def dfs(node):
if node is None:
return
dfs(node.left)
res.append(node.val)
dfs(node.right)后序遍历：
def dfs(node):
if node is None:
return
dfs(node.left)
dfs(node.right)
res.append(node.val)二叉树的迭代遍历
二叉树的迭代遍历主要使用栈来实现，与递归遍历不同，如果使用迭代遍历来处理二叉树，那么需要注意前中后三种遍历的写法存在很大差别。
迭代法前序遍历
前序遍历时的处理逻辑是中左右，如果使用迭代法我们要注意栈是后进先出，所以为了模拟出中左右的顺序，我们需要先把根节点压入栈中，根节点出栈后，然后再压入右孩子节点，最后压入左孩子节点，这样才能使得出栈顺序为中左右。
这边借用代码随想录的动画gif模拟过程：
根据以上原理，写出如下实现方式：
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = [root]
ans = []
while stack:
node = stack.pop()
ans.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return ans迭代法中序遍历
迭代法和递归法不同，在递归法里我们只要对前序遍历的处理顺序稍作修改就能得到中序遍历的写法，但由于中序遍历需要一直访问到左孩子的叶子节点上才会回溯开始遍历，中序遍历存在处理顺序和访问顺序不一致的问题。
在使用迭代法写中序遍历时，需要借用指针的遍历来帮助访问节点，栈主要用来处理节点上的元素。
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = []
res = []
cur = root
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res迭代法后序遍历
后序遍历和前序遍历比较相似，我们只需要对前序遍历的处理顺序稍作修改就能得到后序遍历，具体修改过程如下：
后序遍历的实现写法如下：
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = [root]
res = []
while stack:
node = stack.pop()
res.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return res[::-1]二叉树的层序遍历
层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。
需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。
层序遍历具体实现如下：
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
queue = collections.deque([root])
res = []
while queue:
levelSize = len(queue)
for _ in range(levelSize):
node = queue.popleft()
res.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return res总结
今天主要是对二叉树的基础概念进行了解，首先根据遍历方式分为深度优先遍历DFS和广度优先遍历BFS，再往下进一步细分出前中后序遍历和层序遍历。更进一步，对二叉树进行遍历又有递归遍历和迭代遍历两种，递归和迭代都能用于前中后序遍历，层序遍历主要使用迭代遍历。
