30007：数组二叉搜索树验证

题目

验证数组中的结点是否构成从 root 可达、无环、无共享子树且键严格有序的二叉搜索树。

解析

验证每个结点时携带一个由祖先产生的开区间 (lower, upper)。边界是否存在用两个布尔值表示，因而不需要对 INT64_MIN 或 INT64_MAX 做加减。state 数组用来区分未访问、当前路径和已经完成的结点：再次遇到非零状态说明出现环或共享子树。遍历结束后还要确认每个数组结点都被访问，否则就是不可达垃圾结点。

答案

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

typedef struct {
    int64_t key;
    size_t left;
    size_t right;
} BstNode;

static bool validate_node(
    const BstNode *nodes,
    size_t count,
    size_t index,
    unsigned char *state,
    bool has_lower,
    int64_t lower,
    bool has_upper,
    int64_t upper
) {
    if (index == SIZE_MAX || index >= count || state[index] != 0) {
        return false;
    }
    const BstNode *node = &nodes[index];
    if ((has_lower && node->key <= lower) ||
        (has_upper && node->key >= upper)) {
        return false;
    }

    state[index] = 1;
    if (node->left != SIZE_MAX &&
        !validate_node(
            nodes, count, node->left, state,
            has_lower, lower, true, node->key
        )) {
        return false;
    }
    if (node->right != SIZE_MAX &&
        !validate_node(
            nodes, count, node->right, state,
            true, node->key, has_upper, upper
        )) {
        return false;
    }
    state[index] = 2;
    return true;
}

bool bst_validate(
    const BstNode *nodes,
    size_t count,
    size_t root
) {
    if (count == 0) {
        return root == SIZE_MAX;
    }
    if (nodes == NULL || root == SIZE_MAX || root >= count ||
        count > SIZE_MAX / sizeof(unsigned char)) {
        return false;
    }
    unsigned char *state = calloc(count, sizeof *state);
    if (state == NULL) {
        return false;
    }
    bool valid = validate_node(
        nodes, count, root, state,
        false, 0, false, 0
    );
    if (valid) {
        for (size_t i = 0; i < count; ++i) {
            if (state[i] != 2) {
                valid = false;
                break;
            }
        }
    }
    free(state);
    return valid;
}

每个结点只进入验证函数一次，因此时间复杂度为 $O(n)$，state 和递归调用帧共同占用 $O(n)$ 额外空间。