【LC刷题系列】【持续更新】二叉树问题

遍历问题：

• 二叉树的遍历分为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;
    }