可上 欧弟OJ系统 练习华子OD、大厂真题
绿色聊天软件戳 od1441了解算法冲刺训练（备注【CSDN】否则不通过）

文章目录

相关推荐阅读

题目练习网址：【DFS】2025C-计算三叉搜索树的高度

题目描述与示例

题目描述：

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

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

查找的规则是：

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

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

输入描述

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

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

输出描述

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

示例一

输入

5
5000 2000 5000 8000 1800

输出

3

说明

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

在这里插入图片描述

示例二

输入

3
5000 4000 3000

输出

3

说明

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

在这里插入图片描述

示例三

输入

9
5000 2000 5000 8000 1800 7500 4500 1400 8100

输出

4

说明

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

在这里插入图片描述

解题思路

这道题题面不长，但对于没有接触过搜索树的概念的同学来说，可能是比较费解的。

节点的表示

本题的节点最好通过构建节点类class Node来表示。之所以使用节点类而非邻接表，是因为邻接表要求节点的值是唯一的。但在示例中显然节点的值不唯一，因此使用邻接表来建树并不方便。三叉树的节点类可以用如下代码表示：

# 构建树节点类
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.mid  = None
        self.right = None

三叉搜索树的节点插入过程（举例说明）

假设此时这棵三叉搜索树已经构建了一部分。譬如

在这里插入图片描述

此时我们要往这棵树中插入值为8100的节点，其过程应为：

  1. 从根节点5000出发，比较5000和8100之间的大小关系。8100 - 5000 > 500，故该节点应该位于根节点5000的右子树中。

在这里插入图片描述

  1. 发现根节点5000的右节点8000已经存在，则进行递归，进一步比较8000和8100之间的大小关系。abs(8100 - 8000) <= 500，故该节点应该位于节点8000的中间子树中。

在这里插入图片描述

  1. 发现节点8000的中间节点7500已经存在，则进行递归，进一步比较7500和8100之间的大小关系。8100 - 7500 > 500，故该节点应该位于节点7500的右子树中。

在这里插入图片描述

  1. 发现节点7500的右节点为空，此时将值为8100的节点插入节点7500的右节点。这样就完成了搜索树的插入操作。

在这里插入图片描述

三叉搜索树的节点插入过程（递归三要素）

注意到上述每一步的过程都是类似的，显然可以用递归来实现。考虑递归****三要素。

  1. 递归子问题
    • 插入节点insert_node的值insert_node.val和当前节点cur_node的值cur_node.val比较。若
      • insert_node.val - cur_node.val > 500，则插入节点insert_node应该位于当前节点cur_node的右子树的位置。若此时cur_node的右节点cur_node.right不为空，则对cur_node.right进行递归调用。
      • insert_node.val - cur_node.val < -500，则插入节点insert_node应该位于当前节点cur_node的左子树的位置。若此时cur_node的左节点cur_node.left不为空，则对cur_node.left进行递归调用。
      • abs(insert_node.val - cur_node.val) <= 500，则插入节点insert_node应该位于当前节点cur_node的中间子树的位置。若此时cur_node的中间节点cur_mid.mid不为空，则对cur_node.mid进行递归调用。
  2. 递归终止条件
    • 做完上述判断后，若当前节点cur_node的对应子节点为空，说明insert_node可以插入在cur_node的对应节点位置。插入完毕，递归终止。
  3. 递归入口
    • 除了根节点，其他节点都要从根节点出发进行比较和判断，故递归入口为插入节点insert_node和根节点root进行比较。

想清楚上述过程之后，建树的大致框架就已经能够完成了。其代码如下：

def dfs(cur_node, val):
    if val - cur_node.val  < -500:
        if cur_node.left is None:
            cur_node.left = Node(val)
            return
        dfs(cur_node.left, val)
    elif val - cur_node.val > 500:
        if cur_node.right is None:
            cur_node.right = Node(val)
            return
        dfs(cur_node.right, val)
    else:
        if cur_node.mid is None:
            cur_node.mid = Node(val)
            return
        dfs(cur_node.mid, val)

上述过程的单次时间复杂度为O(logn)，由于对于的每一个新插入的val都必须调用上述函数

计算树的高度

注意本题的设问是计算树的高度。这个问题有两种解决方案，同学们可以自行选择自己喜欢的方案来进行。在效率上，前者是略微优于后者的，因此后者需要在建树结束之后，对整棵树再做一次时间复杂度为O(n)的遍历，但总时间复杂度不变。

在建树过程中计算树的高度

可以在递归函数中多维护一个变量cur_depth表示当前节点cur_node的深度，同时维护一个全局变量ans表示全局的最大深度，一边建树一遍同时更新当前树的最大高度。

在对子节点进行递归调用时，由于子节点的高度始终比当前节点大1，所以应该将cur_depth+1作为子节点的高度传入递归函数中。

在递归终止即进行节点插入时，进行ans和cur_depth+1的比较。之所以是cur_depth+1，是因为进行节点插入后，该节点插入后的高度应该比当前节点高度+1。故dfs()递归函数可以修改为

def dfs(cur_node, val, cur_depth):
    global ans
    if val - cur_node.val < -500:
        if cur_node.left is None:
            cur_node.left = Node(val)
            ans = max(ans, cur_depth + 1)
            return
        dfs(cur_node.left, val, cur_depth + 1)
    elif val - cur_node.val > 500:
        if cur_node.right is None:
            cur_node.right = Node(val)
            ans = max(ans, cur_depth + 1)
            return
        dfs(cur_node.right, val, cur_depth + 1)
    else:
        if cur_node.mid is None:
            cur_node.mid = Node(val)
            ans = max(ans, cur_depth + 1)
            return
        dfs(cur_node.mid, val, cur_depth + 1)

在建树完毕后计算树的高度

同样使用递归完成。其过程类似于LeetCode104. 二叉树的最大深度。其核心的递归函数代码如下

def dfs_cal_height(node, cur_depth):
    if node == None:
        return
    global ans
    ans = max(cur_depth, ans)
    dfs_cal_height(node.left, cur_depth+1)
    dfs_cal_height(node.mid, cur_depth+1)
    dfs_cal_height(node.right, cur_depth+1)

代码

解法一：建树过程中计算树的高度

Python

# 题目：【DFS】2024E/2025C-计算三叉搜索树的高度
# 分值：200
# 作者：闭着眼睛学数理化
# 算法：DFS/树（解法一：建树过程中计算树的高度）
# 代码看不懂的地方，请直接在群上提问


# 构建树节点类
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.mid = None
        self.right = None


# 创建dfs函数，用于对树插入值为val的节点
# 参数cur_node表示与val进行比较的当前节点
# 参数cur_depth表示当前深度
def dfs(cur_node, val, cur_depth):
    global ans
    # 插入节点insert_node位于当前节点cur_node左子树的情况
    if val - cur_node.val < -500:
        # 若cur_node的左节点不存在，则新建插入节点
        # insert_node = Node(val)
        # 并将其插入cur_node的左节点中
        if cur_node.left is None:
            cur_node.left = Node(val)
            # 插入该节点后，最终深度为当前深度+1，故ans应该与cur_depth+1进行比较
            ans = max(ans, cur_depth + 1)
            return
        # 否则对左节点进行递归调用，继续比较，同时深度+1
        dfs(cur_node.left, val, cur_depth + 1)
    # 插入节点insert_node位于当前节点cur_node右子树的情况
    elif val - cur_node.val > 500:
        # 若cur_node的右节点不存在，则新建插入节点
        # insert_node = Node(val)
        # 并将其插入cur_node的右节点中
        if cur_node.right is None:
            cur_node.right = Node(val)
            # 插入该节点后，最终深度为当前深度+1，故ans应该与cur_depth+1进行比较
            ans = max(ans, cur_depth + 1)
            return
        # 否则对右节点进行递归调用，继续比较，同时深度+1
        dfs(cur_node.right, val, cur_depth + 1)
    # 插入节点insert_node位于当前节点cur_node中间子树的情况
    else:
        # 若cur_node的终极那节点不存在，则新建插入节点
        # insert_node = Node(val)
        # 并将其插入cur_node的中间节点中
        if cur_node.mid is None:
            cur_node.mid = Node(val)
            # 插入该节点后，最终深度为当前深度+1，故ans应该与cur_depth+1进行比较
            ans = max(ans, cur_depth + 1)
            return
        # 否则对中间节点进行递归调用，继续比较，同时深度+1
        dfs(cur_node.mid, val, cur_depth + 1)


# 输入节点数目n
n = int(input())
# 输入节点值数组vals
vals = list(map(int, input().split()))
# 构建根节点，根节点的值一定为vals数组中的第一个元素
root = Node(vals[0])
# 答案变量
ans = 1
# 遍历除了根节点以外的其他节点的值val
# 这个值对应插入节点insert_node
for val in vals[1:]:
    # 对于每一个节点的值val，都调用dfs函数
    # 递归入口传入根节点root，插入新的值为val的节点
    # 当前深度为1
    dfs(root, val, 1)

print(ans)

Java

import java.util.Scanner;

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

    Node(int val) {
        this.val = val;
        this.left = null;
        this.mid = null;
        this.right = null;
    }
}

public class Main {
    static int ans = 1;

    static void dfs(Node curNode, int val, int curDepth) {
        if (val - curNode.val < -500) {
            if (curNode.left == null) {
                curNode.left = new Node(val);
                ans = Math.max(ans, curDepth + 1);
                return;
            }
            dfs(curNode.left, val, curDepth + 1);
        } else if (val - curNode.val > 500) {
            if (curNode.right == null) {
                curNode.right = new Node(val);
                ans = Math.max(ans, curDepth + 1);
                return;
            }
            dfs(curNode.right, val, curDepth + 1);
        } else {
            if (curNode.mid == null) {
                curNode.mid = new Node(val);
                ans = Math.max(ans, curDepth + 1);
                return;
            }
            dfs(curNode.mid, val, curDepth + 1);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] vals = new int[n];
        for (int i = 0; i < n; i++) {
            vals[i] = scanner.nextInt();
        }

        Node root = new Node(vals[0]);
        for (int i = 1; i < n; i++) {
            dfs(root, vals[i], 1);
        }

        System.out.println(ans);
    }
}

C++

#include <iostream>
#include <vector>

using namespace std;

struct Node {
    int val;
    Node* left;
    Node* mid;
    Node* right;

    Node(int val) : val(val), left(nullptr), mid(nullptr), right(nullptr) {}
};

int ans = 1;

void dfs(Node* curNode, int val, int curDepth) {
    if (val - curNode->val < -500) {
        if (curNode->left == nullptr) {
            curNode->left = new Node(val);
            ans = max(ans, curDepth + 1);
            return;
        }
        dfs(curNode->left, val, curDepth + 1);
    } else if (val - curNode->val > 500) {
        if (curNode->right == nullptr) {
            curNode->right = new Node(val);
            ans = max(ans, curDepth + 1);
            return;
        }
        dfs(curNode->right, val, curDepth + 1);
    } else {
        if (curNode->mid == nullptr) {
            curNode->mid = new Node(val);
            ans = max(ans, curDepth + 1);
            return;
        }
        dfs(curNode->mid, val, curDepth + 1);
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> vals(n);
    for (int i = 0; i < n; i++) {
        cin >> vals[i];
    }

    Node* root = new Node(vals[0]);
    for (int i = 1; i < n; i++) {
        dfs(root, vals[i], 1);
    }

    cout << ans << endl;

    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>

// 定义树节点结构
typedef struct Node {
    int val;          // 节点的值
    struct Node* left;   // 左子树
    struct Node* mid;    // 中间子树
    struct Node* right;  // 右子树
} Node;

// 全局变量：答案变量
int ans = 1;

// 创建节点的函数
Node* createNode(int val) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->val = val;
    newNode->left = newNode->mid = newNode->right = NULL;
    return newNode;
}

// dfs 函数用于插入节点并计算树的高度
void dfs(Node* curNode, int val, int curDepth) {
    // 插入节点位于当前节点的左子树
    if (val - curNode->val < -500) {
        if (curNode->left == NULL) {
            curNode->left = createNode(val);
            ans = (curDepth + 1 > ans) ? curDepth + 1 : ans;
            return;
        }
        dfs(curNode->left, val, curDepth + 1);
    } else if (val - curNode->val > 500) { // 插入节点位于当前节点的右子树
        if (curNode->right == NULL) {
            curNode->right = createNode(val);
            ans = (curDepth + 1 > ans) ? curDepth + 1 : ans;
            return;
        }
        dfs(curNode->right, val, curDepth + 1);
    } else { // 插入节点位于当前节点的中间子树
        if (curNode->mid == NULL) {
            curNode->mid = createNode(val);
            ans = (curDepth + 1 > ans) ? curDepth + 1 : ans;
            return;
        }
        dfs(curNode->mid, val, curDepth + 1);
    }
}

int main() {
    int n;
    // 输入节点数目
    scanf("%d", &n);

    int* vals = (int*)malloc(n * sizeof(int));  // 存储节点值
    // 输入节点值数组
    for (int i = 0; i < n; i++) {
        scanf("%d", &vals[i]);
    }

    // 创建根节点
    Node* root = createNode(vals[0]);

    // 遍历除了根节点以外的其他节点
    for (int i = 1; i < n; i++) {
        dfs(root, vals[i], 1);  // 插入节点并更新树的高度
    }

    // 输出最大高度
    printf("%d\n", ans);

    // 释放内存
    free(vals);
    return 0;
}

Node JavaScript

const readline = require('readline');

// 创建输入接口
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

// 定义树节点类
class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.mid = null;
    this.right = null;
  }
}

// 全局变量：答案变量
let ans = 1;

// dfs 函数，用于插入节点并计算树的高度
function dfs(curNode, val, curDepth) {
  // 插入节点位于当前节点的左子树
  if (val - curNode.val < -500) {
    if (curNode.left === null) {
      curNode.left = new Node(val);
      ans = Math.max(ans, curDepth + 1);
      return;
    }
    dfs(curNode.left, val, curDepth + 1);
  } else if (val - curNode.val > 500) { // 插入节点位于当前节点的右子树
    if (curNode.right === null) {
      curNode.right = new Node(val);
      ans = Math.max(ans, curDepth + 1);
      return;
    }
    dfs(curNode.right, val, curDepth + 1);
  } else { // 插入节点位于当前节点的中间子树
    if (curNode.mid === null) {
      curNode.mid = new Node(val);
      ans = Math.max(ans, curDepth + 1);
      return;
    }
    dfs(curNode.mid, val, curDepth + 1);
  }
}

// 读取输入数据并处理
rl.question('', (n) => {
  n = parseInt(n); // 读取节点数
  rl.question('', (vals) => {
    // 读取节点值数组
    const valsArr = vals.split(' ').map(Number);
    
    // 创建根节点
    const root = new Node(valsArr[0]);
    
    // 遍历其他节点并调用 dfs 函数
    for (let i = 1; i < n; i++) {
      dfs(root, valsArr[i], 1);
    }

    // 输出树的高度
    console.log(ans);
    
    // 关闭输入接口
    rl.close();
  });
});

Go

package main

import (
        "fmt"
        "math"
)

// 定义树节点结构
type Node struct {
        val   int
        left  *Node
        mid   *Node
        right *Node
}

// 全局变量：答案变量
var ans int = 1

// dfs 函数用于插入节点并计算树的高度
func dfs(curNode *Node, val, curDepth int) {
        // 插入节点位于当前节点的左子树
        if val-curNode.val < -500 {
                if curNode.left == nil {
                        curNode.left = &Node{val: val}
                        ans = int(math.Max(float64(ans), float64(curDepth+1)))
                        return
                }
                dfs(curNode.left, val, curDepth+1)
        } else if val-curNode.val > 500 { // 插入节点位于当前节点的右子树
                if curNode.right == nil {
                        curNode.right = &Node{val: val}
                        ans = int(math.Max(float64(ans), float64(curDepth+1)))
                        return
                }
                dfs(curNode.right, val, curDepth+1)
        } else { // 插入节点位于当前节点的中间子树
                if curNode.mid == nil {
                        curNode.mid = &Node{val: val}
                        ans = int(math.Max(float64(ans), float64(curDepth+1)))
                        return
                }
                dfs(curNode.mid, val, curDepth+1)
        }
}

func main() {
        var n int
        fmt.Scan(&n)

        var vals = make([]int, n)
        for i := 0; i < n; i++ {
                fmt.Scan(&vals[i])
        }

        // 创建根节点
        root := &Node{val: vals[0]}

        // 遍历除了根节点以外的其他节点
        for i := 1; i < n; i++ {
                dfs(root, vals[i], 1) // 插入节点并更新树的高度
        }

        // 输出最大高度
        fmt.Println(ans)
}

解法二：建树完毕后计算树的高度

Python

# 题目：【DFS】2024E/2025C-计算三叉搜索树的高度
# 分值：200
# 作者：闭着眼睛学数理化
# 算法：DFS/树（解法二：建树完毕后计算树的高度）
# 代码看不懂的地方，请直接在群上提问


# 构建树节点类
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.mid = None
        self.right = None


# 创建dfs函数，用于对树插入值为val的节点
# 参数cur_node表示与val进行比较的当前节点
def dfs(cur_node, val):
    # 插入节点insert_node位于当前节点cur_node左子树的情况
    if val - cur_node.val < -500:
        # 若cur_node的左节点不存在，则新建插入节点
        # insert_node = Node(val)
        # 并将其插入cur_node的左节点中
        if cur_node.left is None:
            cur_node.left = Node(val)
            return
        # 否则对左节点进行递归调用，继续比较
        dfs(cur_node.left, val)
    # 插入节点insert_node位于当前节点cur_node右子树的情况
    elif val - cur_node.val > 500:
        # 若cur_node的右节点不存在，则新建插入节点
        # insert_node = Node(val)
        # 并将其插入cur_node的右节点中
        if cur_node.right is None:
            cur_node.right = Node(val)
            return
        # 否则对右节点进行递归调用，继续比较
        dfs(cur_node.right, val)
    # 插入节点insert_node位于当前节点cur_node中间子树的情况
    else:
        # 若cur_node的终极那节点不存在，则新建插入节点
        # insert_node = Node(val)
        # 并将其插入cur_node的中间节点中
        if cur_node.mid is None:
            cur_node.mid = Node(val)
            return
        # 否则对中间节点进行递归调用，继续比较
        dfs(cur_node.mid, val)


# 用于计算树高度的递归函数
# node为当前节点，cur_depth为当前高度
def dfs_cal_height(node, cur_depth):
    if node == None:
        return
    global ans
    ans = max(cur_depth, ans)
    dfs_cal_height(node.left, cur_depth+1)
    dfs_cal_height(node.mid, cur_depth+1)
    dfs_cal_height(node.right, cur_depth+1)


# 输入节点数目n
n = int(input())
# 输入节点值数组vals
vals = list(map(int, input().split()))
# 构建根节点，根节点的值一定为vals数组中的第一个元素
root = Node(vals[0])

# 遍历除了根节点以外的其他节点的值val
# 这个值对应插入节点insert_node
for val in vals[1:]:
    # 对于每一个节点的值val，都调用dfs函数
    # 递归入口传入根节点root，插入新的值为val的节点
    dfs(root, val)


ans = 1
# 计算树的高度的函数，递归调用一次即可，传入节点为根节点和起始高度1
dfs_cal_height(root, 1)

print(ans)

Java

import java.util.Scanner;

class Main {
    static class Node {
        int val;
        Node left, mid, right;

        Node(int val) {
            this.val = val;
        }
    }

    static int ans = 1;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] vals = new int[n];
        for (int i = 0; i < n; i++) {
            vals[i] = scanner.nextInt();
        }

        Node root = new Node(vals[0]);

        for (int i = 1; i < n; i++) {
            dfs(root, vals[i]);
        }

        dfs_cal_height(root, 1);

        System.out.println(ans);
    }

    static void dfs(Node curNode, int val) {
        if (val - curNode.val < -500) {
            if (curNode.left == null) {
                curNode.left = new Node(val);
                return;
            }
            dfs(curNode.left, val);
        } else if (val - curNode.val > 500) {
            if (curNode.right == null) {
                curNode.right = new Node(val);
                return;
            }
            dfs(curNode.right, val);
        } else {
            if (curNode.mid == null) {
                curNode.mid = new Node(val);
                return;
            }
            dfs(curNode.mid, val);
        }
    }

    static void dfs_cal_height(Node node, int curDepth) {
        if (node == null) {
            return;
        }
        ans = Math.max(curDepth, ans);
        dfs_cal_height(node.left, curDepth + 1);
        dfs_cal_height(node.mid, curDepth + 1);
        dfs_cal_height(node.right, curDepth + 1);
    }
}

C++

#include <iostream>
#include <vector>
using namespace std;

class Node {
public:
    int val;
    Node* left;
    Node* mid;
    Node* right;

    Node(int val) {
        this->val = val;
        left = nullptr;
        mid = nullptr;
        right = nullptr;
    }
};

int ans = 1;

void dfs(Node* curNode, int val) {
    if (val - curNode->val < -500) {
        if (curNode->left == nullptr) {
            curNode->left = new Node(val);
            return;
        }
        dfs(curNode->left, val);
    } else if (val -  curNode->val > 500) {
        if (curNode->right == nullptr) {
            curNode->right = new Node(val);
            return;
        }
        dfs(curNode->right, val);
    } else {
        if (curNode->mid == nullptr) {
            curNode->mid = new Node(val);
            return;
        }
        dfs(curNode->mid, val);
    }
}

void dfs_cal_height(Node* node, int curDepth) {
    if (node == nullptr) {
        return;
    }
    ans = max(curDepth, ans);
    dfs_cal_height(node->left, curDepth + 1);
    dfs_cal_height(node->mid, curDepth + 1);
    dfs_cal_height(node->right, curDepth + 1);
}

int main() {
    int n;
    cin >> n;
    vector<int> vals(n);

    for (int i = 0; i < n; i++) {
        cin >> vals[i];
    }

    Node* root = new Node(vals[0]);

    for (int i = 1; i < n; i++) {
        dfs(root, vals[i]);
    }

    dfs_cal_height(root, 1);

    cout << ans << endl;

    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>

// 定义树节点结构体
typedef struct Node {
    int val;
    struct Node* left;
    struct Node* mid;
    struct Node* right;
} Node;

// 全局变量：答案变量，用于保存树的最大高度
int ans = 1;

// 创建新节点的函数
Node* createNode(int val) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->val = val;
    newNode->left = NULL;
    newNode->mid = NULL;
    newNode->right = NULL;
    return newNode;
}

// 插入节点的递归函数
void dfs(Node* curNode, int val) {
    // 插入节点位于当前节点的左子树
    if (val - curNode->val < -500) {
        if (curNode->left == NULL) {
            curNode->left = createNode(val);
            return;
        }
        dfs(curNode->left, val);
    }
    // 插入节点位于当前节点的右子树
    else if (val - curNode->val > 500) {
        if (curNode->right == NULL) {
            curNode->right = createNode(val);
            return;
        }
        dfs(curNode->right, val);
    }
    // 插入节点位于当前节点的中间子树
    else {
        if (curNode->mid == NULL) {
            curNode->mid = createNode(val);
            return;
        }
        dfs(curNode->mid, val);
    }
}

// 用于计算树的高度的递归函数
void dfs_cal_height(Node* node, int cur_depth) {
    if (node == NULL) {
        return;
    }
    // 更新树的最大深度
    if (cur_depth > ans) {
        ans = cur_depth;
    }
    // 递归遍历左子树、右子树和中间子树
    dfs_cal_height(node->left, cur_depth + 1);
    dfs_cal_height(node->mid, cur_depth + 1);
    dfs_cal_height(node->right, cur_depth + 1);
}

int main() {
    int n;
    // 输入节点数目
    scanf("%d", &n);
    int* vals = (int*)malloc(n * sizeof(int));
    
    // 输入节点值数组
    for (int i = 0; i < n; i++) {
        scanf("%d", &vals[i]);
    }

    // 创建根节点，根节点的值为vals数组中的第一个元素
    Node* root = createNode(vals[0]);

    // 遍历除了根节点以外的其他节点的值，进行插入
    for (int i = 1; i < n; i++) {
        dfs(root, vals[i]);
    }

    // 计算树的高度
    dfs_cal_height(root, 1);

    // 输出树的最大高度
    printf("%d\n", ans);

    // 释放分配的内存
    free(vals);

    return 0;
}

Node JavaScript

const readline = require('readline');

// 创建 readline 接口来从标准输入中读取数据
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.mid = null;
    this.right = null;
  }
}

// 创建 dfs 函数，用于对树插入值为 val 的节点
function dfs(curNode, val) {
  // 插入节点位于当前节点的左子树
  if (val - curNode.val < -500) {
    if (curNode.left === null) {
      curNode.left = new Node(val);
      return;
    }
    dfs(curNode.left, val);
  }
  // 插入节点位于当前节点的右子树
  else if (val - curNode.val > 500) {
    if (curNode.right === null) {
      curNode.right = new Node(val);
      return;
    }
    dfs(curNode.right, val);
  }
  // 插入节点位于当前节点的中间子树
  else {
    if (curNode.mid === null) {
      curNode.mid = new Node(val);
      return;
    }
    dfs(curNode.mid, val);
  }
}

// 用于计算树高度的递归函数
function dfs_cal_height(node, curDepth) {
  if (node === null) return;

  // 更新树的最大高度
  ans = Math.max(curDepth, ans);

  // 递归计算左子树、中间子树、右子树的高度
  dfs_cal_height(node.left, curDepth + 1);
  dfs_cal_height(node.mid, curDepth + 1);
  dfs_cal_height(node.right, curDepth + 1);
}

let ans = 1;

// 读取节点数目
rl.question('', (n) => {
  n = parseInt(n); // 将输入的字符串转换为整数

  // 读取节点值数组
  rl.question('', (input) => {
    const vals = input.split(' ').map(Number); // 将输入的字符串按空格分割并转换为数字数组

    // 构建根节点，根节点的值为 vals 数组中的第一个元素
    let root = new Node(vals[0]);

    // 遍历除了根节点以外的其他节点的值，进行插入
    for (let i = 1; i < n; i++) {
      dfs(root, vals[i]);
    }

    // 计算树的高度
    dfs_cal_height(root, 1);

    // 输出树的最大高度
    console.log(ans);

    // 关闭 readline 接口
    rl.close();
  });
});

Go

package main

import "fmt"

// 定义树节点结构体
type Node struct {
        val   int
        left  *Node
        mid   *Node
        right *Node
}

// 用于对树插入值为 val 的节点
func dfs(curNode *Node, val int) {
        // 插入节点位于当前节点的左子树
        if val-curNode.val < -500 {
                if curNode.left == nil {
                        curNode.left = &Node{val: val}
                        return
                }
                dfs(curNode.left, val)
        } else if val-curNode.val > 500 {
                // 插入节点位于当前节点的右子树
                if curNode.right == nil {
                        curNode.right = &Node{val: val}
                        return
                }
                dfs(curNode.right, val)
        } else {
                // 插入节点位于当前节点的中间子树
                if curNode.mid == nil {
                        curNode.mid = &Node{val: val}
                        return
                }
                dfs(curNode.mid, val)
        }
}

// 用于计算树高度的递归函数
func dfsCalHeight(node *Node, curDepth int) {
        if node == nil {
                return
        }
        // 更新树的最大深度
        if curDepth > ans {
                ans = curDepth
        }
        // 递归计算左子树、中间子树、右子树的高度
        dfsCalHeight(node.left, curDepth+1)
        dfsCalHeight(node.mid, curDepth+1)
        dfsCalHeight(node.right, curDepth+1)
}

var ans int

func main() {
        // 输入节点数目
        var n int
        fmt.Scan(&n)

        // 输入节点值数组
        vals := make([]int, n)
        for i := 0; i < n; i++ {
                fmt.Scan(&vals[i])
        }

        // 创建根节点，根节点的值为 vals 数组中的第一个元素
        root := &Node{val: vals[0]}

        // 遍历除了根节点以外的其他节点的值，进行插入
        for i := 1; i < n; i++ {
                dfs(root, vals[i])
        }

        // 计算树的高度
        dfsCalHeight(root, 1)

        // 输出树的最大高度
        fmt.Println(ans)
}

时空复杂度

时间复杂度：O(NlogN)。建树的时间复杂度。

空间复杂度：O(N)。树所占空间。

华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华子OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务1000+同学成功上岸！

  • 课程讲师为全网200w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 90+天陪伴式学习，100+直播课时，300+动画图解视频，500+LeetCode经典题，500+华为OD真题/大厂真题，还有简历修改、模拟面试、陪伴小群、资深HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1441或了解更多

# 算法 # 深度优先 # 宽度优先 # c++ # java # python
Logo
亚马逊云科技技术品牌专区

更多推荐

cover

WRB1205S-1WR2 与钡特电源 VB1-12S05S 参数规格解析｜ 1W 宽压输入隔离 DC-DC 工业电源模块性能拆解

avatar 亚马逊云科技技术品牌专区
cover

人工智能如何改变学习方式

avatar 亚马逊云科技技术品牌专区
cover

AI技术正在改变

avatar 亚马逊云科技技术品牌专区