TOP101题解 | BM37#二叉搜索树的最近公共祖先#
二叉搜索树的最近公共祖先
https://www.nowcoder.com/practice/d9820119321945f588ed6a26f0a6991f
/** * 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; }#TOP101#
TOP101-BM系列 文章被收录于专栏
系列的题解