题目描述：

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

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

查找的规则是：

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

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

输入描述：

第一行为一个数 N，表示有 N个数，1<=N<=10000

第二行为N 个空格分隔的整数，每个数的范围为 [1,10000]

输出描述：

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

示例1

输入：

5
5000 2000 5000 8000 1800

输出：

3

说明：

最终构造出的树高度为3：

示例2

输入：

3
5000 4000 3000

输出：

3

说明：

最终构造出的树高度为3：

解题思路

构建树木的同时，即可计算出树木的高度

源码 Java

public class ThreeTree {
	static  Input input ;
	static {
		input = new Input("5\n" +
				"5000 2000 5000 8000 1800");
		input = new Input("3\n" +
				"5000 4000 3000");
	}
	public static void main(String[] args) {
		int n = Integer.parseInt(input.nextLine());
		if (n == 1) {
			System.out.println(1);
		} else {

			String[] nodes = input.nextLine().split(" ");
			TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
			int hight = 1;
			for (int i = 1; i < n; i++) {
				hight = Math.max(insertNode(root, Integer.parseInt(nodes[i])), hight);
			}
			System.out.println(hight + 1);
		}
	}

	public static int insertNode(TreeNode root, int val) {
		if (root.val - 500 > val) {
			if (root.left != null) {
				return insertNode(root.left, val) + 1;
			} else {
				root.left = new TreeNode(val);
				return 1;
			}
		} else if (root.val + 500 > val) {
			if (root.right != null) {
				return insertNode(root.right, val) + 1;
			} else {
				root.right = new TreeNode(val);
				return 1;
			}
		} else {
			if (root.center != null) {
				return insertNode(root.center, val) + 1;
			} else{
				root.left = new TreeNode(val);
				return 1;
			}
		}
	}
}