2020-07-12【还是树】

最近特别喜欢海浪，希望他带给我力量

今日鸡汤

在不甘心或者不愿意的状态下去做一件事情的时候，我们往往就会把这件事情无意识搞砸。

我始终相信，每件事情都有它合适的契机，与社会或他人无关，只与自己有关，当契机到来的时候，一切都会顺理成章。

今天继续来看树，一大早起来就处理了一个BST的问题——如何判断一棵满二叉树是否为二叉搜索树。
一些知识点：

• 二叉搜索树（Binary Search Tree），它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。（由这个性质可知，我们再判断左右孩子是不是BST树时，一定要传入老祖宗的值进行比较；另外，也可通过BST树的中序遍历是递增的这个性质来做。）
• 满二叉树，除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树（由这个性质可知，我们可以通过下标来判断树的结构，即某个下标为i的节点，其左孩子下标为2n+1，右孩子下标为2n。

另外，注意一些临界条件，比如空树是BST树。

由于输入是层次遍历的值，于是从手撕建树开始。

public class Main{
    public static String NULLNODE = "None";
    // Define tree node structure.
    public class TreeNode{
        int value = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val){
        value = val;
        }
    }
    
    public boolean isBST(TreeNode root, int min, int max){
        if(root == null)    return true;
        int rootVal = root.value;
        if(rootVal <= min || rootVal >= max){
            return false;
        } else{
            return isBST(root.left, min, rootVal ) && isBST(root.right, rootVal, max);
        }
    }
    
    public TreeNode createTree(ArrayList<String> levelTreeNodes, int rootIndex){
        int nodeSize = levelTreeNodes.size();
        if(rootIndex >= nodeSize) {
            return null;
        }
        // Create root node.
        String nodeValue = levelTreeNodes.get(rootIndex);
        // Check whether it is null.
        if(NULLNODE.equals(nodeValue)){
            return null;
        } else{
            TreeNode root = new TreeNode(Integer.parseInt(nodeValue));
            // Create left sub tree.
            int leftIndex = (rootIndex + 1) * 2 - 1;
            root.left = createTree(levelTreeNodes, leftIndex);        
            // Create right sub tree.
            int rightIndex = (rootIndex + 1) * 2;
            root.right = createTree(levelTreeNodes, rightIndex);

            return root;
        }
    }
    
    public static void main(String[] args){
        ArrayList<String> nodes = new ArrayList<String>();
       
        Scanner sc = new Scanner(System.in);
        String inputLine = null;
        if(sc.hasNextLine()) {
            inputLine = sc.nextLine();
        }
        String[] node = inputLine.split(",");
        for(String str: node) {
            nodes.add(str);
        }
        Main main = new Main();
        TreeNode tree = main.createTree(nodes, 0);
        if(main.isBST(tree, 0, Integer.MAX_VALUE)){
            System.out.print("True");
        } else{
            System.out.print("False");
        }
        sc.close();
    }
}