算法学习笔记【day5】二叉树算法

老规矩上链接

二叉树的定义
二叉树节点结构（有点像双向链表）
class Node {
V value;
Node left;
Node right；
}
用递归和非递归两种方式实现二叉树的先序、中序、后序遍历二叉树得先中后序又称为深度优先遍历。
遍历顺序如下：（实际上就是跟节点在前中后的顺序）。
前序遍历：根结点 ---> 左子树 ---> 右子树
中序遍历：左子树---> 根结点 ---> 右子树
后序遍历：左子树 ---> 右子树 ---> 根结点
实现上都可以通过递归序转变而来。
如下图所示：

文章图片

【算法学习笔记【day5】二叉树】但如果不用递归的话，其实就是模拟手动压栈的过程
以中序遍历为例: 每次就是整棵树左边界进栈，依次弹出的过程当中，对弹出节点右侧子节点重复此过程
已上图为例先压1 在压2 再压4。那么先弹4。无右侧子节点弹2有右侧，对5进行此操作，弹5，没了。弹1 有右侧重复，压3 压6 弹6 弹3 有右弹7。
原理是什么呢？原理其实就是任何树都能靠左边界来分解举个例子：

文章图片

层序优先遍历（宽度优先遍历）思路：使用队列，放入该节点，弹出，然后先放左再放右循环往复
还是以上图为例：先放1 弹1 再放2放3 弹2放4放5 弹3放6放7

public static void w(Node head) { if(head == null) { return； } Queue queue = new LinkedList?>(); queue.add(head)； while(!queue. isEmpty()){ Node cur = queue.pol1()； System.out.printin(cur.value)； if(cur.left I=nul1) { queue.add(cur. left)； } if(cur.right l=nul1) { queue. add(cur.right)； } }

相关题目：求一颗二叉树最大宽度
二叉树的相关概念及其实现判断
如何判断一颗二叉树是否是搜索二叉树？
搜索二叉树概念: 每一个子树。左树都比他小，右数都比他大。
解决思路：dfs（深度优先遍历）的时候判断下。或者如果是中序遍历得话直接就是从小到大排序
如何判断一颗二叉树是完全二叉树？
完全二叉树概念：
如何判断一颗二叉树是否是满二叉树？
如何判断一颗二叉树是否是平衡二叉树？（二叉树题目套路）