树

先序遍历：对于每一个子树，先输出头节 点，再输出左节点，最后输出右节点

中序遍历：对于每一个子树，先输出左节点，再输出头结点，最后输出右节点

后序遍历：对于每一个子树，先输出左节点，再输出右节点，最后输出头结点

递归实现，主要是输出value语句的放置地方不一样，放在遍历左右子树之前为先序，放在中间为中序，放在后面为后序

不使用递归实现：

先序遍历：

创建一个栈，按照图中1）2）3）4）顺序运行

后序遍历：

创建两个栈，按照1）2）3）顺序重复执行，打印收集栈

中序遍历：

创建一个栈，把每棵子树整颗树的左边界进栈，依次弹出过程中打印，若有右节树存入栈重复

深度优先遍历：就是二叉树的先序遍历

宽度优先遍历：

非递归写法：创建一个队列，先把头结点放入队列，1）弹出并打印，2）先存左节点再存右节点为空不放，重复1）2）

计算树的宽度：

准备一个队列和一个map先把头结点放入，map中存节点以及节点所在层数，在代码while后面加一个return Math.max(max, CurLevelNodes)

不使用哈希表（map）：

一个队列，两个node类型的指针，存当前层最后一个节点，一个存下一层的最后一个节点，一个int类型存当前层节点数，max存最多节点数，先存入头结点，1）判断该节点是否是最后一个人节点，是max=curLevel，curlevel置0，若不是curLevel加1，2）存入该节点的左右孩子（先左后右），nextend存最后进入队列的节点，3）若当前节点为该层最后一个节点，curend=nextend，否则继续从队列弹出节点，重复1）2）3）

搜索二叉树：

一个节点的左树的节点比其小，右树的节点比其大（一个经典的搜索二叉树中可以认为是没有重复值的）

判断方法：利用树的中序遍历，若全是升序，则是搜索二叉树

递归方法实现：

非递归方法实现：

判断是否为完全二叉树：

使用宽度优先遍历，只要有一个人节点违反1）2）其中之一就不是完全二叉树

判断是否为满二叉树：

判断是否为平衡二叉树：

对于任何一个子树来说，左树的高度和它右树的高度差不超过一

二叉树的递归套路：

在递归中确认对于某个节点，其左子树，和右子树需要返回什么信息来进行判断，以此信息创建结构体

使用地方：对于树的树型DP问题，即可以通过向左树和右树要信息可以解决的问题

例题：

后继结点：在中序遍历中一个节点的下一个遍历的节点便为后继节点

前驱节点：在中序遍历中一个节点的前一个遍历的节点便为前驱节点

能否做到该代码的时间复杂度为O(K)（K为目标节点与该节点的后继结点的距离）

（1）x有右树的时候，x的右树的最左边的节点便为x的后继结点

（2）x无右树时：若x为某节点的左树的最右一个节点则该节点便为x的后驱节点，若x为整颗树最右边的节点则x无后继节点

树的序列化和反序列化：

先序遍历序列化：

#代表空，_代表一个节点的结束，其余如中序，后序，层序，深度遍历的序列化都可以道理相同

serialBypre为先序序列化，reconByoreStribg为反序列化

解决方法：树的中序遍历