二叉树的遍历

5.2 54分

递归遍历

• 略

  非递归遍历

  前序遍历

• 前序遍历为先遍历左子树，后访问节点，再遍历右子树

• 算法实现 通过指针遍历并且使用辅助栈结构 首先指针指向根节点 依次指针往左树移动把节点加入栈中，当指针指向null时候代表没有值了，弹出栈顶打印，将指针指向弹出元素的右节点，执行下个循环

  中序遍历

  后序遍历

  二叉树判断

  6.2 8分
  

  判断搜索二叉树

• 中序遍历 如果一直是升序则一定是搜索二叉树 通过改造中序遍历的代码

  判断完全二叉树

1. 任意一个节点不能有右无左 否则直接返回false
2. 在满足1的基础上如果遇到左右不全的情况（叶子或者有左无右），那么这个节点以后的节点全是叶子几点

• 实现：利用宽度优先遍历每个节点 用变量保存遇到左右不全的情况 然后遍历每个节点满不满足1 如果满足1的话 flag = true 后续遍历根据flag判断 2条件 是不是叶子结点

  判断满二叉树

1. 麻烦的方法 节点个数为N 深度为l 利用公式计算 先统计最大深度 然后再统计节点个数

1. 递归方法 结构体中包含了树的高度以及节点个数 最后获得根节点的高度和节点在用公司判断

   判断平衡二叉树

• 定义一个结构体 里面包含两个变量一个是isBalenced 是否平衡 一个变量是height树的高度 从根节点开始递归求 左子树 和右子树 的平衡和高度 然后返回当前节点的树的高度和平衡性（左右子树高度相差<=1）

  二叉树的递归套路

• 上面的判断二叉搜索树和满二叉树以及平衡二叉树都可以 递归去求解 注意递归的可能性罗列

  两节点最低公共祖先

  第六章 1小时24分
  

• 两个节点的最近公共祖先的意思是 两个节点网上寻找 第一次交汇处

1. 第一种方法 在遍历二叉树的时候 保存每个节点的链 比如 D->B F->E->B 然后遍历链找到公共祖先 具体实现可以用fatherMap来保存 节点之间的父子关系 然后把其中一个节点的链保存到set里面 最后遍历第二个节点的链 如果set中的节点等于 遍历时候遇到的节点 则公共祖先就是这个节点

-

1. 第二种方法难以理解。

二叉树的后继节点

1小时49分

二叉树序列化反序列化

2小时1分

• 下面是两个节点个数和值相同的二叉树 怎么序列化
• 通过先序遍历的方式序列化 下划线把值分隔开 #代表null节点

• 算法实现： 首先通过先序遍历把二叉树的节点 按照上面格式加入到队列中，然后反序列通过消费队列还原二叉树

  折纸问题

  2小时11分