22. Height of Binary Search Tree

Origin: Height of Binary Search Tree

Given the root of a binary search tree, return the height of the tree. Height is the number of nodes along the longest path from root to leaf.

Example

Input: n = 7, values = [4, 2, 6, 1, 3, 5, 7], leftChild = [1, 3, 5, -1, -1, -1, -1], rightChild = [2, 4, 6, -1, -1, -1, -1]

Output: 3

Explanation: 树完美平衡，三层：

• Level 1: Node 4 (root)
• Level 2: Nodes 2 和 6
• Level 3: 叶子 1, 3, 5, 7

最长路径从根到叶子有 3 个节点，高度为 3。

Input Format

• 第一行：n（节点数量）
• 接下来 n 行：values 数组的元素（每个一行）
• 下一行：m（leftChild 数组长度）
• 接下来 m 行：leftChild 数组的元素（每个一行）
• 下一行：p（rightChild 数组长度）
• 接下来 p 行：rightChild 数组的元素（每个一行）

leftChild[i] = -1 表示节点 i 没有左子，rightChild[i] = -1 表示没有右子。

Constraints

• 0 <= n <= 1000
• values.length == n
• leftChild.length == n
• rightChild.length == n
• 所有 values 唯一
• leftChild[i] == -1 或 0 <= leftChild[i] < n
• rightChild[i] == -1 或 0 <= rightChild[i] < n
• 左子值 < 父节点值，右子值 > 父节点值（BST 性质）
• 边构成单连通无环图（树）

Output Format

返回一个整数：树的高度（从根到叶子的最长路径上的节点数）。n = 0 时返回 0。

Sample Input 0

1
10
1
-1
1
-1

Sample Output 0

1

Sample Input 1

2
5
3
2
1
-1
2
-1
-1

Sample Output 1

2

---

函数契约

// 输入：values（节点值数组），leftChild（左子索引数组），rightChild（右子索引数组）
// 输出：树的高度（整数，根到叶子最长路径的节点数）
// 边界：n=0 → 0；单节点 → 1；只有左子或只有右子 → 对侧高度+1

边界表

场景	返回什么
n=0（空树）	0
单节点（无子节点）	1
只有左子	左子树高度 + 1
只有右子	右子树高度 + 1
正常场景	max(左子树高度, 右子树高度) + 1

Resolution

我的解法

function getBinarySearchTreeHeight(values: number[], leftChild: number[], rightChild: number[]): number {
    if (values.length === 0) return 0
    if (values.length === 1) return 1
 
    const getHeight = (node: number): number => {
        if (node === -1) return 0
        const leftHeight = getHeight(leftChild[node])
        const rightHeight = getHeight(rightChild[node])
        return Math.max(leftHeight, rightHeight) + 1
    }
 
    return getHeight(0)
}

解题思路

树的高度 = max(左子树高度, 右子树高度) + 1。

递归函数 getHeight(node)：

• node 是 -1（不存在）→ 返回 0（基线条件）
• 否则 → 递归算左子树高度和右子树高度，取最大值加 1

从根节点（索引 0）开始递归，自然算出整棵树的高度。

复杂度

• 时间：O(n)，每个节点访问一次
• 空间：O(h)，h 是树高，递归栈深度等于树高。最坏情况（链表状树）O(n)，平衡树 O(log n)

参考来源

• 相关题型：树
• 相关文章：算法解题流程：从读题到提交的七步