TOP101题解 | BM37#二叉搜索树的最近公共祖先#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * @author Senky
 * @date 2023.08.04
 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
 * @brief 一个结点可以是自己的祖先，说明这两个结点可能会是父子关系
 *        对于二叉搜索树:层序遍历,第一个元素值介于(p,q]之间的结点就是其公共祖先
 * @param root TreeNode类 
 * @param p int整型 
 * @param q int整型 
 * @return int整型
 */

 //队列元素结构体
#include <stdlib.h>
#define Max(a,b) (a>b?a:b)
#define Min(a,b) (a<b?a:b)
struct QueueNode
 {
    struct TreeNode* tree_node;
    struct QueueNode* next;
 };

//队列结构体
 struct Queue
 {
    struct QueueNode* front;
    struct QueueNode* rear;
    int length;
 };

 //创建空队
 struct Queue* Queue_create()
 {
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->front = queue->rear = NULL;
    queue->length = 0;

    return queue;
 }

 //队列判空
 bool QueueIsEmpty(struct Queue* queue)
 {
    return queue->length == 0;
 }

 //入队
 void Queue_in(struct Queue* queue, struct TreeNode* tree_node)
 {
    struct QueueNode* queue_NewNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
    queue_NewNode->tree_node = tree_node;
    queue_NewNode->next = NULL;

    if(QueueIsEmpty(queue))
    {
        queue->front = queue->rear = queue_NewNode;
    }
    else 
    {
        queue->rear->next = queue_NewNode;
        queue->rear = queue_NewNode;
    }
    queue->length++;
 }

 //出队
 struct TreeNode* Queue_out(struct Queue* queue)
 {
    struct QueueNode* temp = queue->front;
    struct TreeNode* tree_node = queue->front->tree_node;

    if(queue->length == 1)
    {
        queue->front = queue->rear = NULL;
    } 
    else 
    {
        queue->front = queue->front->next; 
    }

    free(temp);
    queue->length--;

    return tree_node;
 }

 //搜索最近的公共祖先
int lowestCommonAncestor(struct TreeNode* root, int p, int q ) 
{
    // write code here
    //结点总数范围:[3,1000],根节点必定不为空
    struct Queue* queue = Queue_create();
    Queue_in(queue, root);

    //将p,q的值排序
    int min = Min(p, q);
    int max = Max(p, q);

    while (!QueueIsEmpty(queue)) 
    {
        struct TreeNode* tree = Queue_out(queue);
        //找到第一个符合要求的值就是祖先结点
        if (tree->val > min && tree->val <= max) 
        {
            return tree->val;
        }

        if(tree->left) Queue_in(queue, tree->left);
        if(tree->right) Queue_in(queue, tree->right);
    }
    return 0;

}