C语言实现二叉树查找离根最近可被3整除节点的问题求解

编写C语言函数，针对给定的二叉有序树，返回指向距离根节点最近、节点值可被3整除的节点的指针。

你写的代码存在两个核心问题，导致结果错误：

• 遍历逻辑不符合需求：距离根节点最近的节点是按层从上到下分布的，同层节点到根的距离相等。你的代码采用深度优先逻辑，只要左子树存在就直接递归遍历左子树，完全不检查同层的右子树节点，会把更深层的左子树节点误判为最近节点。举个典型场景：根节点值为1（不满足），右孩子值为3（第二层，距离根1），左孩子值为2（不满足，其左孩子值为3在第三层，距离根2），你的代码会优先遍历左子树返回第三层的节点，结果完全错误。
• 边界分支缺失返回值：当遍历到左右子树都为空的叶子节点、且节点值不满足整除3的条件时，函数没有写return语句，会触发C语言的未定义行为，运行时可能返回随机无效地址。

要找距离根最近的符合条件节点，最直接高效的方式是用广度优先搜索（层序遍历）：从根节点开始，按层逐个检查节点，第一个满足「值可被3整除」的节点就是答案，找到后可以直接返回，不需要遍历更深层的节点，时间效率最优。

如果不想使用队列做BFS，也可以用带深度记录的深度优先搜索，遍历过程中记录找到的符合条件节点的最小深度，最终返回对应深度的节点，遇到符合条件的节点时可以直接剪枝，不需要继续遍历它的子节点（子节点深度一定比当前节点大，不可能更近）。

BFS层序实现（推荐） #

#include <stdlib.h>
#include <limits.h>

// 二叉树节点结构定义
typedef struct Node {
    int number;
    struct Node *left;
    struct Node *right;
} Node;

// 简易队列结构，用于存储层序遍历的节点指针
typedef struct Queue {
    Node** buf;
    int front;
    int rear;
    int cap;
} Queue;

static Queue* queue_init(int init_cap) {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->buf = (Node**)malloc(sizeof(Node*) * init_cap);
    q->front = q->rear = 0;
    q->cap = init_cap;
    return q;
}

static void queue_push(Queue* q, Node* node) {
    q->buf[q->rear++] = node;
}

static Node* queue_pop(Queue* q) {
    return q->buf[q->front++];
}

static int queue_empty(Queue* q) {
    return q->front == q->rear;
}

static void queue_destroy(Queue* q) {
    free(q->buf);
    free(q);
}

Node* find_closest(Node* root) {
    if (root == NULL) return NULL;
    // 初始队列容量可根据树的实际规模调整，也可自行实现动态扩容逻辑
    Queue* q = queue_init(1024);
    queue_push(q, root);

    Node* res = NULL;
    while (!queue_empty(q)) {
        Node* cur = queue_pop(q);
        if (cur->number % 3 == 0) {
            res = cur;
            break;
        }
        if (cur->left) queue_push(q, cur->left);
        if (cur->right) queue_push(q, cur->right);
    }

    queue_destroy(q);
    return res;
}

递归DFS实现（无额外队列空间） #

#include <limits.h>

// 二叉树节点结构定义
typedef struct Node {
    int number;
    struct Node *left;
    struct Node *right;
} Node;

static void dfs(Node* cur, int cur_depth, int* min_depth, Node** res) {
    if (cur == NULL) return;
    if (cur->number % 3 == 0) {
        if (cur_depth < *min_depth) {
            *min_depth = cur_depth;
            *res = cur;
        }
        // 子节点深度一定大于当前节点，直接剪枝返回
        return;
    }
    dfs(cur->left, cur_depth + 1, min_depth, res);
    dfs(cur->right, cur_depth + 1, min_depth, res);
}

Node* find_closest(Node* root) {
    if (root == NULL) return NULL;
    int min_depth = INT_MAX;
    Node* res = NULL;
    dfs(root, 0, &min_depth, &res);
    return res;
}

内容的提问来源于stack exchange，提问作者smth