Java日记2018-06-26

33. 二叉搜索树的后序遍历序列
    以数组｛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);
    }

34. 二叉树中和为某一值的路径
    递归的实现，栈弹入弹出的时机选择还蛮妙，测试数据时候猜测+试验出来，理解了一下结果

//二叉树中和为某一值的路径
    public static void findpath(TreeNode root, int target) {
        if (root == null)
            return;
        Stack<Integer> path = new Stack<Integer>();
        findpathcore(root, target, path);
    }

    public static void findpathcore(TreeNode root, int target, Stack<Integer> path) {
        if (root == null)
            return;
        //注意push即pop的位置，要在判断外边，这样弹出时候能弹出到最外层，蛮抽象，再看时候可能会更理解……
        path.push(root.val);
        if (root.left == null && root.right == null) {
            if (target == root.val) {
                //path.push(root.val);
                for (int i : path) {
                    System.out.print(i + " ");
                }
                System.out.println(" ");
            }
        } else {
            //path.push(root.val);
            findpathcore(root.left, target - root.val, path);
            findpathcore(root.right, target - root.val, path);
            //path.pop();
        }
        path.pop();
    }