BST 查找最值与二叉树的高度

p30（6 分钟）、p31（7 分钟）

找最小值#

BST 里左边一定更小，所以最小值就是一路往左走到底的那个节点。

1
int findMin(struct btNode *root) {
2
    if (root == NULL) {
3
        printf("Error: Tree is empty\n");
4
        return -1;
5
    }
6
    while (root->left != NULL)
7
        root = root->left;
8
    return root->data;
9
}

直接拿参数 root 往下走就行，不用另开临时指针——root 是局部变量，改它不影响调用方。

例：15 → 10 → 8，8 没有左孩子，就是最小值。

空树得先挡一下。返回什么自己定，如果确定树里全是正数，拿 −1 当哨兵就够。

递归版就是把「一直往左」说成「在左子树里找最小值」：

1
int findMin(struct btNode *root) {
2
    if (root == NULL) { printf("Error: Tree is empty\n"); return -1; }
3
    else if (root->left == NULL) return root->data;   // 到底了
4
    else return findMin(root->left);
5
}

第二个 else if 是递归出口。最小值不可能在右子树里，所以左子树一空就已经知道答案了。

最大值对称，一路往右。

二叉树的高度#

先把定义钉死，不然后面全是坑：

1
高度 = 从某节点到最远叶子，路径上的「边数」
2
空树高度 = −1
3
叶节点高度 = 0
4
单节点树高度 = 0
5
树的高度 = 根的高度

另一种定义是数「节点个数」而不是边数，那样叶节点高度是 1、空树是 0。这些笔记里一律用边数。

深度是反方向：

节点	深度	高度
根	0	3
节点 2	1	2
叶子 9	3	0

深度从根往下数，高度从叶子往上数，同一个节点这两个值通常不一样。

树的高度 = 所有节点里最大的深度，所以「高度」和「最大深度」有时会混着说。

求高度#

1
高度(节点) = max(高度(左), 高度(右)) + 1

那个 +1 是「节点连到自己子树的那条边」。

1
int findHeight(struct btNode *root) {
2
    if (root == NULL) return -1;
3
    return max(findHeight(root->left), findHeight(root->right)) + 1;
4
}

递归出口为什么是 −1#

这里容易记错，我第一遍就写成了 0。

拿叶子节点看：它左右都是 NULL，会发起两次空调用。这两次该返回什么？

1
返回 0  →  叶子高度 = max(0,0) + 1 = 1    ✗ 叶子应该是 0
2
返回 −1 →  叶子高度 = max(−1,−1) + 1 = 0   ✓

−1 正好抵消那个 +1：空节点本身不存在，但公式里从父节点连过去的那条边被算了一次，得减掉。

复杂度#

求高度是 O(N)，不是 O(h)。

因为不知道哪边更深，必须两边都算，每个节点都要访问一次。

操作	复杂度
findMin / findMax	O(h)
findHeight	O(N)

坑#

findMin 往左、findMax 往右，别记反。
空树不判空会解引用 NULL。
递归出口返回 0 会让所有高度集体差 1。
max(...) + 1 的 +1 别漏。
求高度是 O(N)，别按 O(h) 估。