本文主要是介绍JZ68 二叉搜索树的最近公共祖先，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
二叉搜索树的最近公共祖先_牛客题霸_牛客网
描述
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.
2.二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值
3.所有节点的值都是唯一的。
4.p、q 为不同节点且均存在于给定的二叉搜索树中。
数据范围:
3<=节点总数<=10000
0<=节点值<=10000
解题思路：递归 or 迭代。
根结点作为当前结点，如果p < root < q|| q<root < p, 说明根结点就是祖先
如果 root >p && root > q: 去左子树找到 第一个p < root <= q|| q<root=<p的root结点
如果root > p && root > q: 去右子树找到 第一个p < root <= q || q<root=<p 的root结点
不会去左子树和右子树去查的情况：p<root<=q || q< root <=p,当前结点就是祖先
/*** struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param root TreeNode类 * @param p int整型 * @param q int整型 * @return int整型*/int lowestCommonAncestor(TreeNode* root, int p, int q) {// write code here//Solution 1: recursive// if(!root) return -1;// if(root->val > p && root->val > q) // return lowestCommonAncestor(root->left, p, q);// if(root->val < p && root->val < q)// return lowestCommonAncestor(root->right, p, q);// return root->val;//Solution 2: No recursiveTreeNode *pCur = root;while(pCur && pCur->val > p && pCur->val > q) pCur = pCur->left;while(pCur && pCur->val < p && pCur->val < q) pCur = pCur->right;//不会去左子树和右子树去查的情况：p<pCur->val<=q || q<pCur<=p,当前结点就是祖先 return pCur->val;}
};这篇关于JZ68 二叉搜索树的最近公共祖先的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
