185.二叉树：二叉搜索树的最近公共祖先（力扣）

本文主要是介绍185.二叉树：二叉搜索树的最近公共祖先（力扣），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

代码解决

/*** 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 的值，则当前节点即为最低公共祖先。

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

1. 首先判断当前节点是否为空，如果为空，返回空。
2. 根据 p 和 q 的值与当前节点的值的关系，决定在左子树或右子树中寻找这两个节点。
3. 递归地在选定的子树中寻找节点 p 和 q。
4. 根据递归的结果，判断当前节点是否为最低公共祖先，并返回结果。

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

这篇关于185.二叉树：二叉搜索树的最近公共祖先（力扣）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---