C语言 | Leetcode C语言题解之第236题二叉树的最近公共祖先
题目：
题解：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/typedef struct road_t
{struct TreeNode *road_node; // 途径路径struct road_t *p_next;
}ROAD_T;int road_fill(struct TreeNode* root, struct TreeNode* p, ROAD_T *road_node_now) // 路径填充
{ROAD_T *new_node = NULL;int flag = 0;if(!root){return 0;}if(root == p) // 找到节点置起标志位，将途径路径存储{flag = 1;}flag |= road_fill(root->left, p, road_node_now);flag |= road_fill(root->right, p, road_node_now);if(flag){new_node = (ROAD_T *)malloc(1 * sizeof(ROAD_T));if(!new_node){printf("open space error");exit(0);}new_node->road_node = root;new_node->p_next = road_node_now->p_next;road_node_now->p_next = new_node;return flag;}return 0;
}struct TreeNode *find_sncestor(ROAD_T *road_head_p, ROAD_T *road_head_q) // 寻找公共节点
{ROAD_T *now_p_node = road_head_p->p_next;ROAD_T *now_q_node = road_head_q->p_next;ROAD_T *last_same_node = NULL;while(now_p_node){now_q_node = road_head_q;while(now_q_node){if(now_p_node->road_node == now_q_node->road_node){last_same_node = now_p_node->road_node;}now_q_node = now_q_node->p_next;}now_p_node = now_p_node->p_next;}return last_same_node;
}struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {ROAD_T *road_head_p = (ROAD_T *)calloc(1, sizeof(ROAD_T));ROAD_T *road_head_q = (ROAD_T *)calloc(1, sizeof(ROAD_T));if(!road_head_q || !road_head_p){printf("open space error");exit(0);}road_fill(root, p, road_head_p); // 新建p节点路径road_fill(root, q, road_head_q); // 新建q节点路径return find_sncestor(road_head_p, road_head_q);
}