PAT 1115. Counting Nodes in a BST (30) Java版

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

• The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Insert a sequence of numbers into an initially empty binary search tree. Then you are supposed to count the total number of nodes in the lowest 2 levels of the resulting tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=1000) which is the size of the input sequence. Then given in the next line are the N integers in [-1000 1000] which are supposed to be inserted into an initially empty binary search tree.

Output Specification:

For each case, print in one line the numbers of nodes in the lowest 2 levels of the resulting tree in the format: n1 + n2 = n where n1 is the number of nodes in the lowest level, n2 is that of the level above, and n is the sum.

Sample Input:

9
25 30 42 16 20 20 35 -5 28

Sample Output:

2 + 4 = 6

建立二叉搜索树，然后求最后两个的节点个数

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    private static List<Node> list = new ArrayList<>();
    private static int h = 0;

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());
        String[] values = bufferedReader.readLine().split(" ");
        if (n >= 1 && n <= 1000) {
            Node root = new Node(Integer.parseInt(values[0]), 1);
            list.add(root);
            h = 1;
            for (int i = 1; i < values.length; i++) {
                insertNode(root, Integer.parseInt(values[i]), 1);
            }
            int n1 = 0, n2 = 0;
            for (Node node : list) {
                if (node.height == h) {
                    n1++;
                } else if (node.height == h - 1) {
                    n2++;
                }
            }

            System.out.println(n1 + " + " + n2 + " = " + (n1 + n2));
        }
    }

    private static void insertNode(Node root, int val, int high) {
        if (val <= root.val) {
            if (root.left != null) {
                insertNode(root.left, val, high + 1);
            } else {
                root.left = new Node(val, high + 1);
                h = h < root.left.height ? root.left.height : h;
                list.add(root.left);
            }

        } else {
            if (root.right != null) {
                insertNode(root.right, val, high + 1);
            } else {
                root.right = new Node(val, high + 1);
                h = h < root.right.height ? root.right.height : h;
                list.add(root.right);
            }
        }
    }
}

class Node {
    Node left, right;
    int val, height;

    public Node(int val, int height) {
        this.val = val;
        this.height = height;
        this.left = this.right = null;
    }
}