Java日记2018-06-04

32.3 按之字形顺序打印二叉树
上一题的扩展，使用辅助的队列 和栈来实现，注意一下注释里面顺序的坑

public static void printtree(TreeNode root) {
        LinkedList<TreeNode> que = new LinkedList<TreeNode>();
        Stack<TreeNode> sta = new Stack<TreeNode>();
        boolean reverse = true;
        int count = 0;// 记录当前层已经打印的个数
        int last = 0;// 记录当前层一个有多少个
        int layer = 1;// 当前打印层级
        TreeNode temp = null;
        que.offer(root);
        while (!que.isEmpty()|| !sta.isEmpty()) {
            if (layer % 2 == 1) {
                last = que.size();
                count = 0;
                while (count < last) {
                    //System.out.print("lay:"+layer+" value:"+que.peek().val);
                    System.out.print(que.peek().val);
                    temp = que.poll();
                    if (temp.left != null)
                        sta.add(temp.left);
                    if (temp.right != null)
                        sta.add(temp.right);
                    count++;
                }
                
            } else {
                last = sta.size();
                count = 0;
                while (count < last) {
                    //System.out.print("lay:"+layer+" value:"+sta.peek().val);
                    System.out.print(sta.peek().val);
                    temp = sta.pop();
                    //注意偶数行先存右边，再存左边，试试为啥
                    if (temp.right != null)
                        que.add(temp.right);
                    if (temp.left != null)
                        que.add(temp.left);
                    count++;
                }
                
            }
            layer++;

            System.out.println();
        }
    }

33. 二叉搜索树的后序遍历序列

题解对于后序遍历的举例是错误的

image.png

以数组｛5，7，6，9，11，10，8｝为例，后序遍历结果的最后一个数字8就是根节点的值。在这个数组中，前3个数字5，7和6都比8小，是值为8的结点的左子树结点；后3个数字9，11和10都比8 大，是值为8的结点的右子树结点
于是呢，如果只有两个或者1个数，定义为是真的。具体实现上，先找左边第一个比跟节点（也就是最后一个点）大的值，如果此后的点还存在比根节点小的值，那么就是假的喽，继续递归实现。

public static boolean VerifySquenceOfBST(int[] arr) {
        if(arr==null || arr.length==0) return false;
        return verify(arr,0,arr.length-1);
    }
    public static boolean verify(int[] arr,int start,int end)  {
        if(end-start<=1) return true;
        int cur = start;
        //找到比跟节点大的地方
        while(arr[cur]<arr[end] && cur<end) {
            cur++;
        }
        //后面的节点一旦比根节点还小，就说明不是右子树
        for(int i = cur+1;i<end;i++) {
            if(arr[i]<arr[end]) return false;
        }
        return verify(arr, start, cur - 1) && verify(arr, cur, end - 1);
    }