二叉树的非递归遍历方式（叫写的中序）

1.前序遍历

• ** 递归方式 **(较简单，面试大概率不会考，会让写非递归方式)

public void preOrder(TreeNode root){
	if(root != null){
		System.out.println(root.val);
		preOrder(root.left);
		preOrder(root.right);
	}
}

• ** 非递归方法 **

1. 创建一个栈用来存储节点元素
2. 将根节点入栈，当栈不为空的时候，出栈栈顶元素访问，若元素右子节点不为空，将右子节点入栈，若左子节点不为空，将左子节点入栈（** 顺序不能反：因为需要先递归地遍历左子树，所以加入栈的顺序必须左节点在后才能先被访问到**）

public void preOrder(TreeNode root, List<Integer> list){
	if(root == null){return;}  //节点为空直接返回
	Deque<TreeNode> stack = new LinkedList<>();  //用双端队列来模拟栈
	stack.addFirst(root);  
	while(!stack.isEmpty()){  
		TreeNode node = stack.getFirst();  //访问根节点
		//System.out.println(node.val);
		list.add(node.val);
		stack.removeFirst();  //出栈根节点
		if(node.right!=null){  //入栈右子节点
			stack.addFirst(node.right);
		}
		if(node.left != null){  //入栈左子节点
			stack.addFirst(node.left);
		}
	}
}

2.中序遍历

• ** 递归方式**

public void inOrder(TreeNode root){
	if(root != null){
		inOrder(root.left);
		System.out.println(root.val);
		inOrder(root.right);
	}
}

• ** 非递归方法**
  1.创建栈，创建一个辅助节点初始化为根节点
  2.当栈非空或者辅助节点不为空
  • 若辅助节点不为空，一直往左访问，并将节点入栈，直到遇到最左叶子节点
  • 遇到叶子节点后，访问最左叶子节点，然后将该节点出栈，将辅助节点指向该最左叶子节点的右子节点，访问其右子树

public void inOrder(TreeNode root,List<Integer> list){
	if(root == null){return;}  //节点为空，直接返回
	Deque<TreeNode> stack = new LinkedList<>();  //双端队列模拟栈
	TreeNode node = root;  //辅助节点
	while(! stack.isEmpty()|| node != null){
		if(node != null){  //非叶子节点一直往左访问
			stack.addFirst(node);
			node = node.left;
		}else{//叶子节点
			node = stack.getFirst();  //访问改最左叶子节点
			list.add(node.val);
			stack.removeFirst();  //最左叶子节点出栈
			node = node.right;  //往最左叶子节点的右子树访问
		}
	}
}

3.后序遍历

** 说明：后序遍历是前序遍历的镜像操作，只要操作顺序完全和前序遍历相反就可以，从递归方式也可以看出来**

• ** 递归方式**

public void lastOrder(TreeNode root){
	if(root != null){
		lastOrder(root.left);
		lastOrder(root.right);
		System.out.println(root.val);
	}
}

• ** 非递归方式**
  1.与先序遍历相比的两个相反：（1）节点值加入列表的顺序相反（2）访问左右子节点的顺序相反

public void lastOrder(TreeNode root,List<Integer> list){
	if(root == null){return;}
	Deque<TreeNode> stack = new LinkedList<>();
	stack.addFirst(root);
	while(! stack.isEmpty()){
		TreeNode node = stack.getFirst();
		list.add(0,node.val); //与先序遍历相反，从前面加入节点值
		stack.removeFirst();
		//访问节点的顺序与先序遍历相反
		if(node.left != null){
			stack.addFirst(node.left);
		}
		if(node.right != null){
			stack.addFirst(node.right);
		}	
	}
}

4.层序遍历

• ** 递归方式 **

public class LayerOrder{
    ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    public static ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        layerOrder(root,0);
        return list;
    }
    
    //递归实现
    public void layerOrder(TreeNode root,int level){
        if(root == null){return;}
        if(level == list.size()){
            list.add(new ArrayList<Integer>());
        }
        list.get(level).add(root.val);
        layerOrder(root.left,level+1);
        layerOrder(root.right,level+1);
    }
}

• ** 非递归实现 **

    public static ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        //非递归队列实现
         if(root == null){return new ArrayList<>();}
         Deque<TreeNode> nodes = new LinkedList<>();
         nodes.offer(root);
         ArrayList<ArrayList<Integer>> res = new ArrayList<>();
         while(! nodes.isEmpty()){
             ArrayList<Integer> temp = new ArrayList<>();
             int size =nodes.size();  //注意这里不能直接写入for循环，因为大小是动态变化的
             for(int i=0;i<size;i++){
                 TreeNode tnode = nodes.poll();
                 temp.add(tnode.val);
                 if(tnode.left != null){
                     nodes.offer(tnode.left);
                 }
                  if(tnode.right != null){
                     nodes.offer(tnode.right);
                 }
             }
             res.add(temp);
         }
         return res;
    }

八股文分割线,有空接着学接着更！！

没回答好的问题总结

1.HTTP协议头部有哪些内容，提交一个post请求会设置HTTP头部的哪些东西？

回答：

2.Mysql事务的实现机制？

回答：

3.100万个元素中找最大的100个，怎样做才能高效？

回答：

4.IO多路复用的原理？

回答：

5.ConcurrentHashMap的实现原理？做了哪些优化？

回答：

6.Cookie里边有哪些信息？

回答：

7.一个计数器count多个线程访问，怎样保证线程安全？

回答：	1.加锁（synchronized，RentrantLock）
		2.使用java.util.concurrent包下的原子类