image.png
    image.png
    递归序的概念：每个节点三次访问，
    后面还有moris遍历，有的节点只遍历两遍。
    image.png
    树的递归序：
    image.png
    题目一：二叉树递归和非递归的遍历。
    前序遍历的非递归写法
    左程云的方法：
    step1 : 准备栈，头节点压进去，
    step2 : 弹出的时候打印
    step3 : 先压有孩子，再压做孩子

    image.png
    image.png
    另外：左视频里说错了（5二叉树1:16:40秒处）
    image.png
    解法2: 我的方法，跟中序遍历思想类似，通过将整颗树划分为若干左侧区域

    2.     public static void inOrdr2(Node head){
    3.         if(head == null) return ;
    4.         Stack<Node >stack = new Stack<>();
    5.         Node cur = null;
    6.         process2(head, stack);
    7.         while(stack.size()>0){
    8.             cur =stack.pop();
    9.             System.out.println(cur.value);
    10.             process2(cur.right,stack);
    11.         }
    12.     }
    14.     public static void process2(Node head, Stack<Node >stack){
    15.         while(head !=null){
    16.             stack.add(head);
    17.             head = head.left;
    18.         }
    19.     }
    21.     public static void posOrder(Node head){
    22.         if(head == null) return ;
    23.         posOrder(head.left);
    24.         posOrder(head.right);
    25.         System.out.println(head.value);
    26.     }

    后序遍历非递归
    输出的时候不打印，放到收集栈
    image.png
    image.png
    image.png
    中序遍历：
    image.png
    image.png
    tips：所有树都是可以被左边界分解掉的，这其实是一种遍历顺序，跟数组的对角线顺序类似。
    image.png
    image.png

    题目二： 暴力递归很多思想是用二叉树的遍历，包括用套路求解的题目，求最长的搜索二叉树拓扑结构节点数量。这个也是用后序遍历的思想
    题目三： 根据前序遍历和中序遍历数组，求解后序遍历数组。
    定义好尝试模型，范围上的尝试模型。
    题目四、直观打印树的图示结构
    image.png
    题目五：求树的最大宽度。其实就是图的宽度优先遍历
    tips：
    1、先序遍历就是，深度优先遍历
    2、宽度优先用队列，深度优先用栈。
    3、java里面linkedList双向链表就是队列的实现之一。
    前置问题：宽度优先遍历问题
    解法：用队列记录每一步节点
    image.png

    
    public static void levelOrder(Node head){
        if(head == null) return ;
        Queue<Node > queue = new LinkedList<>();
        queue.add(head);
        Node cur =head;
        while(queue.size() >0){
            cur = queue.poll();
            System.out.println(cur.value);
            if(cur.left != null){
                queue.add(cur.left);
            }
            if(cur.right!=null){
                queue.add(cur.right);
            }
        }
    }

    求最大宽度，
    解法1 ： 用hasmap记录每一层的层号。
    image.png
    tips：
    1、这里用一个curlevel变量跟前一个弹出队列的进行比较来判断是否进入下一层。如果进入下一层，重置该层节点数量。
    2、注意这里的结算时机，当层号发生改变的时候，但是组后一层层号没变，所以当跳出循环的 时候，还要结算一次。
    3、看代码，他设置什么变量，自己也要设置同样的变量。
    解法2: 不用哈希表的方法。
    关键是找到每一层的end节点，当来到此的时候进行结算，开始想最右节点在右边界上，但是右边界可能没有值，毕竟不是完全二叉树，
    采用的办法是，碰到每一个节点都更新下一层结束节点的值，即在结算前不断更新nextEnd的值
    image.png
    左程云：谁进队列，谁就是nextEndNode，永远保持最新节点。
    利用当前end和下一层的end进行滚动更新。

      public static int width(Node head){
        if(head == null )return 0;
        Node curEndNode = head;
        Node nextEndNode = null;
        Queue<Node > queue = new LinkedList<>();
        queue.add(head);
        int max = 0;
        int curWidth = 0;
        Node temp = null;
        while(!queue.isEmpty()){
            temp = queue.poll();
            if(temp.left!=null){
                nextEndNode = temp.left;
                queue.add(temp.left);
            }
            if(temp.right!=null){
                nextEndNode = temp.right;
                queue.add(temp.right);
            }
            if(temp == curEndNode){
                max = Math.max(max , curWidth +1);
                curWidth=0;
                curEndNode = nextEndNode;
            }
            else {
                curWidth ++;
            }
        }
        return max;
    }

    解法3: 这个没懂什么意思，可能就是省了一个max变量，但是结算时机和滚动更新策略应该还是解法2的
    image.png