快手笔试第一题

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class KSP1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String line = in.nextLine().trim();
        if ("None".equals(line) || "".equals(line)) {
            System.out.println("True");
            return;
        }


        String[] numbersStringArray = line.split(",");
        int[] numbers = new int[numbersStringArray.length];
        for (int i = 0; i < numbersStringArray.length; i++) {
            numbers[i] = Integer.parseInt(numbersStringArray[i]);
        }

        Tree root = new Tree();
        int height = (int) (Math.log(numbers.length + 1) / Math.log(2)) - 1;
        buildFullTree(root, height);

        int index = 0;
        LinkedList<Tree> stack = new LinkedList<>();
        stack.addLast(root);

        for (int i = 0; i <= height; i++) {
            int length = stack.size();

            for (int j = 0; j < length; j++) {
                Tree tmp = stack.pop();
                tmp.value = numbers[index++];
                if (tmp.left != null) {
                    stack.add(tmp.left);
                }

                if (tmp.left != null) {
                    stack.add(tmp.right);
                }
            }
        }

        if (isSearchTree(root)) {
            System.out.println("True");
        } else {
            System.out.println("False");
        }


    }

    public static void buildFullTree(Tree root, int n) {
        LinkedList<Tree> stack = new LinkedList<>();
        stack.addLast(root);
        int count = 0;

        do {
            int length = stack.size();
            for (int i = 0; i < length; i++) {
                Tree tmp = stack.pop();
                tmp.left = new Tree();
                tmp.right = new Tree();
                stack.addLast(tmp.left);
                stack.addLast(tmp.right);
            }
        } while (++count < n);
    }

    public static boolean isSearchTree(Tree root) {
        if (root == null) return true;
        Stack<Tree> stack = new Stack<>();
        Tree pre = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (pre != null && root.value <= pre.value) return false;
            pre = root;
            root = root.right;
        }
        return true;
    }


}


class Tree {
    int value;
    Tree left;
    Tree right;

    public Tree(int value) {
        this.value = value;
    }

    public Tree() {
    }
}