本文主要是介绍【leetcode235】二叉搜索树的最近公共祖先，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
示例：
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
解题思路
对于二叉树的问题，我们通常要往递归的思路上去思考。思考递归的关键在于找到子问题，和终止条件。
在本题中子问题是：对于一个根节点，
- 如果节点p和节点q 都在左子树上，那么应该到左子树上去寻找最近公共祖先；
- 如果节点p和节点q都在右子树上，那么应该到右子树上去寻找最近公共祖先；
- 如果节点p和节点q 一个在左子树节点，一个在右子树节点，那么根节点就是最近公共祖先。
终止条件是：对于一个根节点，
- 如果根节点为空，那么就返回空，说明没找到任何一个节点。
- 如果根节点的值与任何一个节点的值相等，就返回根节点，表示找到了其中一个节点。
以上是二叉树, 找到该树中两个指定节点的最近公共祖先的思路。
那么对于二叉搜索树，要明白二叉搜索树的特点：
若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉搜索树
根据这个性质，我们想判断节点p和节点q 是不是在根节点的左子树上，只需要将节点p和节点q 的值和根节点的值进行比较即可。
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root->val < p->val && root->val < q->val){return lowestCommonAncestor(root->right, p, q);}else if(root->val > p->val && root->val > q->val){return lowestCommonAncestor(root->left, p, q);}else{return root;}}
};
复杂度分析
- 时间复杂度：因为二叉树的节点有且只会被访问一次，因此时间复杂度为 O(N)。
- 空间复杂度：递归本质上使用是系统栈，栈的深度取决于二叉树的高度。在最坏情况下二叉树为一条链，此时高度为 N，因此空间复杂度为 O(N)。
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {TreeNode* res = root;while(res){if(res->val > p->val && res->val > q->val){res = res->left;}else if(res->val < p->val && res->val < q->val){res = res->right;}else{break;}}return res;}
};
复杂度分析
- 时间复杂度：因为二叉树的节点有且只会被访问一次，因此时间复杂度为 O(N)。
- 空间复杂度：没有使用辅助的栈，因此空间复杂度为 O(1)。
这篇关于【leetcode235】二叉搜索树的最近公共祖先的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
