C语言实现LeetCode第236题：二叉树的最近公共祖先

在C语言和数据结构的学习中，二叉树是一种非常基础且重要的数据结构。它由节点组成，每个节点包含一个值和最多两个子节点，通常称为左子节点和右子节点。在处理二叉树问题时，经常需要遍历树来完成各种任务，例如搜索特定值、插入节点、删除节点、计算树的高度等。 LeetCode是一个面向计算机科学与软件工程的在线编程平台，它提供各种难度的编程题目供用户练习，旨在帮助用户提高算法和编程技巧。其中，第236题是关于二叉树的问题，题目要求编写一个函数来找出给定二叉树中任意两个节点的最近公共祖先（Lowest Common Ancestor，简称LCA）。 最近公共祖先的定义是：对于任意的两个节点p和q（它们是二叉树中的任意节点），最近公共祖先是所有p和q的祖先节点中，距离它们最近的一个。假设树中每个节点的值都是唯一的，并且p和q两个节点存在于树中。 C语言实现第236题的过程中，需要考虑到几个关键点： 1. 理解递归算法的原理，因为在处理树结构时，递归是一种常见的且有效的解决方案。 2. 确定算法的递归策略。在这个问题中，递归策略是： - 如果当前节点为空，返回空。 - 如果当前节点就是p或q中的一个，那么这个节点就是最近公共祖先。 - 递归地在左子树中查找p和q，如果找到，则返回找到的节点。 - 递归地在右子树中查找p和q，如果找到，则返回找到的节点。 - 如果左子树和右子树中都找到了p和q，则当前节点为最近公共祖先。 3. 实现函数的返回类型应为一个指针类型，指向树节点的指针。 4. 在编写代码时，需要正确处理指针，包括指针的解引用和空指针的情况。 为了更好地理解题目和解决方案，以下是一个典型的C语言题解代码实现： ```c struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) { // 如果当前节点为空或者等于p或q，则返回当前节点 if (root == NULL || root == p || root == q) { return root; } // 递归地在左子树和右子树中查找p和q struct TreeNode* left = lowestCommonAncestor(root->left, p, q); struct TreeNode* right = lowestCommonAncestor(root->right, p, q); // 如果左子树和右子树都找到，则说明当前节点就是最近公共祖先 if (left != NULL && right != NULL) { return root; } // 如果只有左子树或只有右子树找到，则返回找到的那一个节点 return (left != NULL) ? left : right; } ``` 以上代码中，`lowestCommonAncestor`函数通过递归的方式，先从根节点开始，分别在左右子树中查找p和q节点。如果在某侧子树中找到了p或q，则将该侧子树的根节点返回，相当于在搜索过程中，一旦发现p或q的线索，就不会再继续向下搜索，而是返回结果。只有当在左右子树中都找到了线索，才说明当前节点就是最近公共祖先。 此外，还应该注意C语言的基础知识点，例如结构体的定义、指针的操作和递归函数的编写等。熟练掌握这些基础知识点对于解决类似问题至关重要。 总之，LeetCode第236题考察了编程者对二叉树的遍历和递归思想的理解及应用。正确地分析题目并编写出高效的算法代码，是解决这类问题的关键所在。