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); }
文章版权声明:除非注明,否则均为主机测评原创文章,转载或复制请以超链接形式并注明出处。