Java日记2018-05-09

第一题
二叉搜索树的后序遍历序列
二叉搜索树的特点：第一部分是左子树结点的值，它们都比根节点的值小；第二部分是右子树结点的值，他们都比根节点的值大。因此可以通过设置开始点与结束点递归实现，写的时候结束点写成了index，其实写成end最清晰。没写的原因是刚开始没考虑到这样实现

public class VerifySquenceOfBST34 {
    public static boolean verifyBST(int[] array){
        if(array.length<2) return true;
        int index = array.length-1;
        System.out.println("the length is:"+index);
        return verifyBstCore(array,0,index);
    }
    public static boolean verifyBstCore(int[] arr,int start,int index) {
        System.out.println("the star is:"+start+" the index is:"+index);
        int rootindex=0;
        if(index-start<2) return true;
        
        while(arr[rootindex]<arr[index] && rootindex< index) {
            rootindex++;
        }
        System.out.println("the rootindex is:"+rootindex);
        for(int i=rootindex+1;i<index;i++){
            if(arr[i]<arr[index]) return false;
            
        }
        return verifyBstCore(arr,start,rootindex-1) && verifyBstCore(arr,rootindex,index-1);
    
    }
    
    public static void main(String[] args) {
        int[] arr = {5,7,9,6,11,10,8};
        int[] arr2= {5,7,6,9,11,10,8};
        if(verifyBST(arr)) {
            System.out.print("you are the one");
        }
        
    }

}

第二题 二叉树中和为某一值的路径
参考https://blog.csdn.net/jsqfengbao/article/details/47291207
https://www.cnblogs.com/lfeng1205/p/6853918.html?utm_source=itdadao&utm_medium=referral
使用一个stack记录走过的路径，如果符合要求则打印，同时pop当前叶子，回到此叶子的父节点，继续寻找另一个路径

public class BinaryTreeNode {
    int val;
    BinaryTreeNode left;
    BinaryTreeNode right;
    public void BinaryTreeNode(){
        this.val=val;
    }

}

package com.lyc.dataautest;

import java.util.Stack;

public class BinaryTreefindPath {
    public static void findpath(BinaryTreeNode pnode,int k) {
        if(pnode==null) return;
        Stack<Integer> path= new Stack<Integer>();
        findpathcore(pnode,k,path);
    }
    public static void findpathcore(BinaryTreeNode pnode,int k,Stack<Integer> path) {
        if(pnode==null) return;
        if(pnode.left==null&&pnode.right==null) {
            if(pnode.val==k) {
                System.out.println("路径开始");
                //打印路径记录的节点
                for(int i:path) {
                    System.out.print("i is:"+i+",");
                }
                //最后一个节点未push进stack，因此需单独打印
                System.out.println(pnode.val);
            }
        } else {
            path.push(pnode.val);
            findpathcore(pnode.left,k-pnode.val,path);
            findpathcore(pnode.right,k-pnode.val,path);
                       //未发现等于k的路径，需要回退pop
            path.pop();
        }
    }
    
    public static void main(String[] args) {
        BinaryTreeNode root1 = new BinaryTreeNode();  
        BinaryTreeNode node1 = new BinaryTreeNode();  
        BinaryTreeNode node2 = new BinaryTreeNode();  
        BinaryTreeNode node3 = new BinaryTreeNode();  
        BinaryTreeNode node4 = new BinaryTreeNode();  
        BinaryTreeNode node5 = new BinaryTreeNode();  
        BinaryTreeNode node6 = new BinaryTreeNode();  
        root1.left = node1;  
        root1.right = node2;  
        node1.left = node3;  
        node1.right = node4;  
        node4.left = node5;  
        node4.right = node6;  
        root1.val = 8;  
        node1.val = 8;  
        node2.val = 7;  
        node3.val = 9;  
        node4.val = 2;  
        node5.val = 4;  
        node6.val = 7;  
        findpath(root1,25);
    }

}