题目描述：

定义构造三叉搜索树规则如下:

每个节点都存有一个数，当插入一个新的数时，从根节点向下寻找，直到找到一个合适的空节点插入。查找的规则是:

• 1.如果数小于节点的数减去500，则将数插入节点的左子树
• 2.如果数大于节点的数加上500，则将数插入节点的右子树
• 3.否则，将数插入节点的中子树

给你一系列数，请按以上规则，按顺序将数插入树中，构建出一棵三叉搜索树，最后输出树的高度。

输入描述

第一行为一个数N，表示有N个数，1<=N<=10000
第二行为N个空格分隔的整数，每个数的范围为[1,10000]

输出描述

输出树的高度(根节点的高度为1)

示例1

输入 

5

5000 2000 5000 8000 1800

输出

3

/*** 根节点*/static Node root;/*** 节点类*/static class Node {int value;Node left, middle, right;public Node(int value) {this.value = value;left = null;middle = null;right = null;}}public static void main(String[] args) {Scanner in = new Scanner(System.in);int N = in.nextInt();for (int i = 0; i < N; i++) {int num = in.nextInt();insert(num);//插入到三叉树中}int height = getHeight(root);//获取树的高度System.out.println(height);}/*** 获取树的高度** @param root 根节点* @return 返回树的高度*/private static int getHeight(Node root) {if (root == null) {return 0;}int leftHeight = getHeight(root.left);int middleHeigth = getHeight(root.middle);int rightHeighth = getHeight(root.right);return 1 + Math.max(Math.max(leftHeight, middleHeigth), rightHeighth);}/*** 插入节点** @param num 待插入的值*/private static void insert(int num) {root = insertRec(root, num);}/*** 递归插入节点** @param root  当前节点* @param value 待插入的值* @return 返回插入后的节点*/private static Node insertRec(Node root, int value) {if (root == null) {return new Node(value);}if (value < root.value - 500) {root.left = insertRec(root.left, value);} else if (value > root.value + 500) {root.right = insertRec(root.right, value);} else {root.middle = insertRec(root.middle, value);}return root;}

 解题思路

1. 定义一个节点类 Node，包含节点值 value 和三个子节点 left、middle、right。
2. 定义一个静态的根节点 root。
3. 实现插入节点的方法 insert，采用递归方式实现。根据规则将新数插入到合适的子树中。
4. 实现计算树高度的方法 getHeight，同样采用递归方式，返回以当前节点为根的子树的高度。