思路：模拟 本题需要构建出三叉树的结构，根据题面逻辑构建树即可。

三叉树节点定义:

val - 节点值 height - 节点所在高度 left - 左子树 mid - 中子树 right - 右子树 而插入时直接按题意插入即可。具体可见代码。

需要注意的是：我们如何记录最大深度。

方法1：

等插入完，再实现一个dfs搜索这颗三叉树，得到最大深度。

方法2：(更方便)

在插入的时候，多记录一个深度，边插入边更新深度即可。

python

class TreeNode:
    def __init__(self, val):
        self.val = val  # 节点值
        self.height = None  # 节点所在高度
        self.left = None  # 左子树
        self.mid = None  # 中子树
        self.right = None  # 右子树
​
# 插入单个数字到三叉树内
ans = 0 # 最大深度
def insert(root, val , dep):
    global ans
    ans = max(ans, dep) # 更新最大深度
    if root is None:
        return TreeNode(val)
    if val < root.val - 500:
        root.left = insert(root.left, val , dep + 1)
    elif val > root.val + 500:
        root.right = insert(root.right, val , dep + 1)
    else:
        root.mid = insert(root.mid, val , dep + 1)
    return root
​
n = int(input()) # 数组长度
arr = list(map(int, input().split())) # 数组
root = insert(None, arr[0] , 1) # 插入第一个数字
for i in range(1 , n): # 插入剩下的数字
    insert(root, arr[i] , 1) # 插入单个数字到三叉树内
print(ans) # 输出最大深度

c++

#include <iostream>
#include <vector>
using namespace std;
​
class TreeNode {
public:
    int val;  // 节点值
    int height;  // 节点所在高度
    TreeNode* left;  // 左子树
    TreeNode* mid;  // 中子树
    TreeNode* right;  // 右子树
​
    TreeNode(int val) {
        this->val = val;
        this->height = 0;
        this->left = nullptr;
        this->mid = nullptr;
        this->right = nullptr;
    }
};
​
int ans = 0; // 最大深度
​
TreeNode* insert(TreeNode* root, int val, int dep) {
    ans = max(ans, dep); // 更新最大深度
    if (root == nullptr) {
        return new TreeNode(val);
    }
    if (val < root->val - 500) {
        root->left = insert(root->left, val, dep + 1);
    } else if (val > root->val + 500) {
        root->right = insert(root->right, val, dep + 1);
    } else {
        root->mid = insert(root->mid, val, dep + 1);
    }
    return root;
}
​
int main() {
    int n;
    cin >> n; // 数组长度
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    TreeNode* root = insert(nullptr, arr[0], 1); // 插入第一个数字
    for (int i = 1; i < n; i++) { // 插入剩下的数字
        insert(root, arr[i], 1); // 插入单个数字到三叉树内
    }
    cout << ans << endl; // 输出最大深度
​
    return 0;
}

Java

import java.util.*;
class TreeNode {
    int val;  // 节点值
    Integer height;  // 节点所在高度
    TreeNode left;  // 左子树
    TreeNode mid;  // 中子树
    TreeNode right;  // 右子树
​
    public TreeNode(int val) {
        this.val = val;
        this.height = null;
        this.left = null;
        this.mid = null;
        this.right = null;
    }
}
​
public class Main {
    static int ans = 0; // 最大深度
​
    public static TreeNode insert(TreeNode root, int val, int dep) {
        ans = Math.max(ans, dep); // 更新最大深度
        if (root == null) {
            return new TreeNode(val);
        }
        if (val < root.val - 500) {
            root.left = insert(root.left, val, dep + 1);
        } else if (val > root.val + 500) {
            root.right = insert(root.right, val, dep + 1);
        } else {
            root.mid = insert(root.mid, val, dep + 1);
        }
        return root;
    }
​
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 数组长度
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        TreeNode root = insert(null, arr[0], 1); // 插入第一个数字
        for (int i = 1; i < n; i++) { // 插入剩下的数字
            insert(root, arr[i], 1); // 插入单个数字到三叉树内
        }
        System.out.println(ans); // 输出最大深度
    }
}

Js

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
 
class TreeNode {
  constructor(val) {
    this.val = val; // 节点值
    this.height = undefined; // 节点所在高度
    this.left = null; // 左子树
    this.mid = null; // 中子树
    this.right = null; // 右子树
  }
}
 
class Tree {
  constructor() {
    this.root = null; // 树的根节点
    this.height = 0; // 树的高度
  }
 
  add(val) {
    const node = new TreeNode(val);
 
    if (this.root == null) {
      // 如果树是空的，则当前创建的节点将作为根节点
      node.height = 1; // 根节点的高度为1
      this.root = node;
      this.height = 1;
    } else {
      // 如果树不是空的，则从根节点开始比较
      let cur = this.root;
 
      while (true) {
        // 假设创建的节点node是当前节点cur的子节点，则node节点高度值=cur节点高度值+1
        node.height = cur.height + 1;
        // 如果创建的node进入新层，则更新树的高度
        this.height = Math.max(node.height, this.height);
 
        if (val < cur.val - 500) {
          // 如果数小于节点的数减去500，则将数插入cur节点的左子树
          if (cur.left == null) {
            // 如果cur节点没有左子树，则node作为cur节点的左子树
            cur.left = node;
            // 停止探索
            break;
          } else {
            // 否则继续探索
            cur = cur.left;
          }
        } else if (val > cur.val + 500) {
          // 如果数大于节点的数加上500，则将数插入节点的右子树
          if (cur.right == null) {
            cur.right = node;
            break;
          } else {
            cur = cur.right;
          }
        } else {
          // 如果数大于节点的数加上500，则将数插入节点的右子树
          if (cur.mid == null) {
            cur.mid = node;
            break;
          } else {
            cur = cur.mid;
          }
        }
      }
    }
  }
}
 
void (async function () {
  while (true) {
    try {
      const n = parseInt(await readline());
 
      const tree = new Tree();
 
      const nums = (await readline()).split(" ").map(Number);
 
      for (let i = 0; i < n; i++) {
        tree.add(nums[i]);
      }
 
      console.log(tree.height);
    } catch (e) {
      break;
    }
  }
})();

题目描述

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

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

1.如果数小于节点的数减去500，则将数插入节点的左子树

2.如果数大于节点的数加上500，则将数插入节点的右子树

3.否则，将数插入节点的中子树

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

输入描述

第一行为一个数 N，表示有 N 个数，$1 \leq N \leq 10000$

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

输出描述

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

样例1

输入

5
5000 2000 5000 8000 1800

输出

3

说明

最终构造出的树如下高度为3:

样例2

输入

3
5000 4000 3000

输出

3

说明

最终构造出的树如下高度为3:

样例3

输入

9
5000 2000 5000 8000 1800 7500 4500 1400 8100

输出

4

说明

最终构造出的树如下高度为4: