遍历问题：
-
二叉树的遍历分为DFS和BFS，DFS分为前序遍历 中序遍历 后序遍历，通常实现是递归，但是有溢出的可能，所以非递归实现中 前序遍历一般使用stack实现，利用其特性实现，注意 前序遍历的特点是中 左 右 ，所以入栈顺序要先右再左。
前序遍历：public List<Integer> preorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if(root!=null){ Stack<TreeNode> stack = new Stack<>(); stack.push(root); while(!stack.isEmpty()){ root = stack.pop(); result.add(root.val); if(root.right!=null){ stack.push(root.right); } if(root.left!=null){ stack.push(root.left); } } } return result; }中序遍历：：把树看作一个个“撇”，把每个撇逐个入站，然后弹出时候判断是否有右子节点，如果有的话，就把右子节点入展，下一个弹出，这样是根据二叉树中序遍历的特点归纳出来的方法。即：左中右的顺序，左和中都在撇上，右作为单独判断
public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); if(root!=null){ Stack<TreeNode> stack = new Stack<>(); while(!stack.isEmpty()||root!=null){ if(root!=null){ stack.push(root); root = root.left; }else{ root = stack.pop(); list.add(root.val); root = root.right; } }后序遍历：
**层序遍历（DFS）：** 使用队列 先入先出 可以使用标志位 实现监控每一层的结束
```[java]
public List<Integer> zhongxu(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root!=null){
Queue<Integer> queue =new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
root = queue.poll();
list.add(root.val);
if(root.left!=null){
queue.add(root.left);
}
if(root.right!=null){
queue.add(root.right);
}
}102. 二叉树的层序遍历
严格意义上的层序遍历呢 每层要在不同的数组。
是用一个二元组 (node, level) 来表示状态，它表示某个节点和它所在的层数，每个新进队列的节点的 level 值都是父亲节点的 level 值加一。最后根据每个点的 level 对点进行分类，分类的时候我们可以利用linkedHashMap，维护一个以 对应节点值组成的数组 为键，level为值，广度优先搜索结束以后按键 level 从小到大取出所有值，组成答案返回即可
/**
* 层序遍历 一层一个list
* @param root
* @return
*/
public List<List<Integer>> levelOrder(TreeNode root) {
if (root != null) {
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
LinkedHashMap<TreeNode, Integer> levelMap = new LinkedHashMap<>();
levelMap.put(root, 1);
while (!queue.isEmpty()) {
root = queue.poll();
if (root.left != null) {
queue.add(root.left);
levelMap.put(root.left, levelMap.get(root) + 1);
}
if (root.right != null) {
queue.add(root.right);
levelMap.put(root.right, levelMap.get(root) + 1);
}
}
return dothings(levelMap);
}
return new ArrayList<>();
}
/**
* 处理map 转为需要的形式
* @param root
* @return
*/
public List<List<Integer>> dothings(LinkedHashMap<TreeNode,Integer> levelMap){
List<List<Integer>> result = new ArrayList<>();
int lastLevel=0;
Iterator<Map.Entry<TreeNode, Integer>> iterator = levelMap.entrySet().iterator();
while (iterator.hasNext()){
Map.Entry<TreeNode, Integer> next = iterator.next();
if (lastLevel!=next.getValue()){
List<Integer> thisLevel = new ArrayList<>();
thisLevel.add(next.getKey().val);
result.add(thisLevel);
lastLevel = next.getValue();
}else {
result.get(result.size()-1).add(next.getKey().val);
}
}
return result;
}待改进：输出的map可以不是这个形式，map转答案的方法笨重了些，而且严重依赖于linkedHashMap有序的特点，但是没想好用什么方式输出节点和他们的层级关系 转list会方便些。
622.二叉树的最大宽度：我下面的题解是针对null节点不计入宽度的规则实现的，也是用map记录每个节点和它对应的层级，但是想不出怎么计算包含null节点的最大宽度。待解决
public int widthOfBinaryTree(TreeNode root) {
if(root != null){
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
Map<TreeNode,Integer> levelMap =new HashMap<>();
levelMap.put(root,1);
Integer focusOn = 1;//现在在处理哪一层
Integer thisWidth = 0;//当前层宽度 出来时候统计
int max = 0;//用来在层与层之间比较大小使用的值
while(!queue.isEmpty()){
root = queue.poll();
if(root.left!=null){
queue.add(root.left);
levelMap.put(root.left,levelMap.get(root)+1);//下一层入map ,层级+1
}
if(root.right!=null){
queue.add(root.right);
levelMap.put(root.right,levelMap.get(root)+1);
}
if(focusOn.equals(levelMap.get(root))){
thisWidth++;//你确实是这层的人 宽度++
}else{
//如果进入else 证明按层序遍历的下一层的节点出来了 00后诞生
focusOn++;//看下一层
max = Math.max(max,thisWidth);//和上一届最大值相比
thisWidth=1;//宽度给回初始值 因为如果有下层 肯定有节点 最小就是1
}
}
max = Math.max(max,thisWidth);
return max;
}
return 0;
}