首页 > 其他分享 >剑指 Offer 68 - I. 二叉搜索树的最近公共祖先(简单)

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先(简单)

时间:2023-08-20 10:46:50浏览次数:33  
标签:lowestCommonAncestor TreeNode val Offer 祖先 二叉 68 root 节点

题目:

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {      //依旧要利用二叉搜索树的性质
        if(root->val>p->val&&root->val>q->val) return lowestCommonAncestor(root->left, p, q);  //如果当前节点的值大于两个指定节点的值,则公共祖先一定在当前节点的左子树
        if(root->val<p->val&&root->val<q->val) return lowestCommonAncestor(root->right, p, q); //如果当前节点的值小于两个指定节点的值,则公共祖先一定在当前节点的右子树
        return root;      //其他情况包括:空节点、当前节点值介于两者指定节点值之间,说明该节点就是公共祖先
    }
};

以上方法来自代码随想录

标签:lowestCommonAncestor,TreeNode,val,Offer,祖先,二叉,68,root,节点
From: https://www.cnblogs.com/fly-smart/p/17643691.html

相关文章

  • 【剑指Offer】21、栈的压入、弹出序列
    【剑指Offer】21、栈的压入、弹出序列题目描述:输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该......
  • 【剑指Offer】7、斐波那契数列
    【剑指Offer】7、斐波那契数列题目描述:大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。假设n<=39。解题思路:斐波那契数列:0,1,1,2,3,5,8........总结起来就是:第一项是0,第二项是1,后续第n项为第n-1项和第n-2项之和。用公式描述如下:......
  • Gym103687D The Profiteer:回滚莫队信息双指针可以做到线性对数
    标题写得好所谓的回滚莫队信息意思是,设信息保存在两个大小分别为\(a,b\)的结构上,将这两个信息进行合并得到大小为\(a+b\)的信息需要的时间为\(\Omega(\min\{a,b\}\cdotf(n))\);而给定一个大小为\(1\)的信息,可以在\(\mathrmO(f(n))\)时间内将它加入到任何一个结构中......
  • 力扣101. 对称二叉树
    给你一个二叉树的根节点 root ,检查它是否轴对称。 示例1:输入:root=[1,2,2,3,4,4,3]输出:true 示例2:输入:root=[1,2,2,null,3,null,3]输出:false  提示:树中节点数目在范围 [1,1000] 内-100<=Node.val<=100 康复训练1/*2*@lcapp=......
  • 《剑指Offer》-40-最小的 K 个数
    如果直接调用sortAPI然后要几个打印几个就没意思了,应该是和某个排序的内部过程结合首先排除O(N2)的低效率排序算法,最先想到的其实是堆排序,小根堆,但是需要额外的空间其次像快排、归并这样的也不合适……我想到了可以这样,快排第一轮划分之后,将部分舍去……应该就是这样了,堆排......
  • 剑指 Offer 55 - I. 二叉树的深度(简单)
    题目:classSolution{public:voidtraversal(TreeNode*cur,int&max,intdepth){//max用来记录最长路径长度,depth记录当前路径长度if(!cur)return;depth++;if(depth>max)max=depth;traversal(cur->left,max,depth);......
  • 剑指 Offer 54. 二叉搜索树的第k大节点
    方法一:由于是有序的平衡二叉树,因此是中序。根据dfs中序迭代求得递增排序后,再反转就可求得结果。classSolution{public:vector<int>tmp;intkthLargest(TreeNode*root,intk){//if(root!=NULL)returndfs(root);reverse(tmp.be......
  • 合并二叉树
    力扣(LeetCode)官网-全球极客挚爱的技术成长平台经验1:程序写在递归函数前面代表压栈的时候实现,也就是说浏览到这个结点的时候实现程序写在递归函数后面代表弹栈的时候实现,也就是下一次递归结束后在本次递归函数中实现那么到底是压栈的时候实现还是弹栈的时候实现呢,这要看对根......
  • 剑指 Offer 36. 二叉搜索树与双向链表
    本题比较重要的有两点:1.一般认为有序的二叉搜索树,都是中序遍历。2.中序遍历的递归顺序,得到的就是排好序的,就是链表的顺序,因此只需管遍历的过程中的链表指向即可。classSolution{public://pre将来指向尾节点,head指向头节点Node*pre=nullptr,*head=nullptr;......
  • 剑指 Offer 16. 数值的整数次方(中等)
    题目classSolution{public:doubletraversal(doublex,intn){if(n==0)return1.00000;doubley=traversal(x,n/2);//本题需要对递归时的指数进行二分法,否则超时。returnn%2==0?y*y:y*y*x;//y=(x^4)。n=8,则x^8=y*y;n......