二叉树的种类
满二叉树
满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
完全二叉树
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。
二叉搜索树
二叉搜索树是有数值的了，二叉搜索树是一个有序树
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树
平衡二叉搜索树
平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
二叉树的遍历方式
深度优先遍历
前序遍历（中左右）
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
//preorder(root,res);
/*
//迭代法
if(root == null){
return res;
}
Stack<TreeNode> stack = new Stack<>();
//中-右-左 入栈
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur= stack.pop();
res.add(cur.val);
if(cur.right != null){
stack.push(cur.right);
}
if(cur.left != null){
stack.push(cur.left);
}
}
*/
//统一迭代
//要处理的节点放入栈之后，紧接着放入一个空指针作为标记
if(root == null){
return res;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
//右-左-中
TreeNode cur = stack.pop();
if(cur != null){
if(cur.right!=null){
stack.push(cur.right);
}
if(cur.left!=null){
stack.push(cur.left);
}
stack.push(cur);
//中节点访问过，加空节点标记
stack.push(null);
}else{//遇到空节点，才把下个节点放进结果集
cur = stack.peek();
stack.pop();
res.add(cur.val);
}
}
return res;
}
void preorder(TreeNode root,List<Integer> res){
if(root == null){
return;
}
//中-左-右
res.add(root.val);
preorder(root.left,res);
preorder(root.right,res);
}
}
中序遍历（左中右）
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
//inorder(root,res);
/*
//迭代法，中序需要处理，借助指针
//左-右 入栈
if(root == null){
return res;
}
//借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur!=null || !stack.Empty()){
//当前节点不为空，放入栈且一直走到左 底
if(cur!=null){
stack.push(cur);
cur = cur.left;
}else{
//当前节点为空，且栈内有值，弹出上个节点，加入集合，往右走
//没有右端，会继续弹上个
//有右端，就会入栈记录，并走到左端底
cur = stack.pop();//弹的是最左端节点，栈顶是最底端
res.add(cur.val);
cur=cur.right;
}
}
*/
//统一迭代
//要处理的节点放入栈之后，紧接着放入一个空指针作为标记
if(root == null){
return res;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
//右-中-左
TreeNode cur = stack.pop();
if(cur != null){
if(cur.right!=null){
stack.push(cur.right);
}
stack.push(cur);
//中节点访问过，加空节点标记
stack.push(null);
if(cur.left!=null){
stack.push(cur.left);
}
}else{//遇到空节点，才把下个节点放进结果集
cur = stack.peek();
stack.pop();
res.add(cur.val);
}
}
return res;
}
void inorder(TreeNode root,List<Integer> res){
if(root == null){
return;
}
//左-中-右
inorder(root.left,res);
res.add(root.val);
inorder(root.right,res);
}
}
后序遍历（左右中）
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
//postorder(root,res);
/*
//迭代法
if(root == null){
return res;
}
Stack<TreeNode> stack = new Stack<>();
//中-右-左 入栈
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur= stack.pop();
res.add(cur.val);
if(cur.right != null){
stack.push(cur.right);
}
if(cur.left != null){
stack.push(cur.left);
}
}
//反转
Collections.reverse(res);
*/
//统一迭代
//要处理的节点放入栈之后，紧接着放入一个空指针作为标记
if(root == null){
return res;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
//中右左
TreeNode cur = stack.pop();
if(cur != null){
stack.push(cur);
//中节点访问过，加空节点标记
stack.push(null);
if(cur.right!=null){
stack.push(cur.right);
}
if(cur.left!=null){
stack.push(cur.left);
}
}else{//遇到空节点，才把下个节点放进结果集
cur = stack.peek();
stack.pop();
res.add(cur.val);
}
}
return res;
}
void postorder(TreeNode root,List<Integer> res){
if(root == null){
return;
}
postorder(root.left,res);
postorder(root.right,res);
res.add(root.val);
}
}
广度优先遍历
层次遍历
class Solution {
public List<List<Integer>> res = new ArrayList<List<Integer>>();
public List<List<Integer>> levelOrder(TreeNode root) {
order1(root,0);
//order2(root);
return res;
}
//DFS-递归法
public void order1(TreeNode node,Integer deep){
if(node == null){
return;
}
if(res.size() == deep){
List<Integer> list = new ArrayList<Integer>();
res.add(list);
}
res.get(deep).add(node.val);
deep++;
order1(node.left,deep);
order1(node.right,deep);
}
//BFS-迭代法，使用队列
public void order2(TreeNode node){
if(node == null){
return;
}
Queue<TreeNode> que = new LinkedList<TreeNode>();
que.offer(node);
while(!que.isEmpty()){
List<Integer> list = new ArrayList<Integer>();
int deep = que.size();
while(deep> 0){
TreeNode cur = que.poll();
list.add(cur.val);
if(cur.left!=null){
que.offer(cur.left);
}
if(cur.right!=null){
que.offer(cur.right);
}
deep--;
}
res.add(list);
}
}
}
二叉树的定义
public class TreeNode{
int val;
TreeNode left;
TreeNode right;
TreeNode(){}
TreeNode(int val){this.val = val;}
TreeNode(int val,TreeNode left,TreeNode rihgt){
this.val = val;
this.left = left;
this.right = right;
}
}