代码解决
/*** 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 NULL;// 如果当前节点的值大于 p 和 q 的值,说明 p 和 q 都在左子树if(root->val > p->val && root->val > q->val){// 递归查找左子树中的 LCATreeNode* left1 = lowestCommonAncestor(root->left, p, q);// 如果在左子树中找到了 LCA,直接返回if(left1 != NULL) return left1;}// 如果当前节点的值小于 p 和 q 的值,说明 p 和 q 都在右子树if(root->val < p->val && root->val < q->val){// 递归查找右子树中的 LCATreeNode* right1 = lowestCommonAncestor(root->right, p, q);return right1; // 返回右子树中的 LCA}// 如果当前节点的值介于 p 和 q 之间,或者等于 p 或 q 的值,当前节点即为 LCAreturn root;} };
代码使用了递归的方法。主要思路是首先判断当前节点是否为空,如果为空,返回空。然后,根据 p 和 q 的值与当前节点的值的关系,递归地在左子树或右子树中寻找这两个节点。如果当前节点的值大于 p 和 q 的值,则 p 和 q 都在左子树;如果当前节点的值小于 p 和 q 的值,则 p 和 q 都在右子树;如果当前节点的值介于 p 和 q 之间,或者等于 p 或 q 的值,则当前节点即为最低公共祖先。
这里简要解释一下代码的工作流程:
- 首先判断当前节点是否为空,如果为空,返回空。
- 根据 p 和 q 的值与当前节点的值的关系,决定在左子树或右子树中寻找这两个节点。
- 递归地在选定的子树中寻找节点 p 和 q。
- 根据递归的结果,判断当前节点是否为最低公共祖先,并返回结果。
这个算法的时间复杂度是 O(h),其中 h 是树的高度。在最坏的情况下,可能需要遍历整个树来找到最低公共祖先。空间复杂度也是 O(h),因为需要存储递归调用的栈。