代码解决

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:// 函数用于寻找二叉树中节点 p 和 q 的最低公共祖先TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// 如果当前节点为空，直接返回空if(root == NULL) return root;// 如果当前节点是 p 或者 q，直接返回当前节点if(root == p || root == q) return root;// 递归查找左子树中的 LCATreeNode* left = lowestCommonAncestor(root->left, p, q);// 递归查找右子树中的 LCATreeNode* right = lowestCommonAncestor(root->right, p, q);// 如果左子树和右子树都不为空，说明 p 和 q 分别在当前节点的两侧，当前节点是 LCAif(left != NULL && right != NULL) return root;// 如果左子树为空，右子树不为空，说明 LCA 在右子树if(left == NULL && right != NULL){return right;}   // 如果左子树不为空，右子树为空，说明 LCA 在左子树else if(left != NULL && right == NULL){return left;}else{// 左子树和右子树都为空，说明没有找到 LCAreturn NULL;}}
};

代码使用了递归的方法。主要思路是首先判断根节点是否为空，如果为空，返回空。然后，判断根节点是否等于给定的两个节点中的任意一个，如果是，返回根节点。否则，递归地在左子树和右子树中寻找这两个节点，如果两个节点分别在左右子树中找到，则根节点即为最低公共祖先；如果一个节点在左子树中找到，另一个在右子树中找到，则根节点不是最低公共祖先；如果一个节点都没有找到，则根节点也不是最低公共祖先。

这里简要解释一下代码的工作流程：

1. 首先判断根节点是否为空，如果为空，返回空。
2. 判断根节点是否等于给定的两个节点中的任意一个，如果是，返回根节点。
3. 递归地在左子树中寻找节点p和q，同时记录结果。
4. 递归地在右子树中寻找节点p和q，同时记录结果。
5. 检查左右子树的结果：
   • 如果左右子树都找到了节点，则根节点即为最低公共祖先，返回根节点。
   • 如果左子树找到了一个节点，右子树没有找到，则返回左子树的结果。
   • 如果右子树找到了一个节点，左子树没有找到，则返回右子树的结果。
   • 如果左右子树都没有找到节点，则返回空。

这个算法的时间复杂度是 O(n)，其中 n 是树中节点的数量。在最坏的情况下，可能需要遍历整个树来找到最低公共祖先。空间复杂度也是 O(n)，因为需要存储递归调用的栈。