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

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

时间:2023-08-26 20:33:05浏览次数:74  
标签:lowestCommonAncestor right TreeNode Offer II 二叉树 return root left

题目:

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==p||root==q||root==nullptr) return root;      //如果当前节点为空或者当前节点即为其中某个指定节点
        TreeNode* left = lowestCommonAncestor(root->left, p, q);      
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(left&&right) return root;
        if(!left) return right;
        return left;
    }
};

以上代码转自代码随想录

标签:lowestCommonAncestor,right,TreeNode,Offer,II,二叉树,return,root,left
From: https://www.cnblogs.com/fly-smart/p/17659407.html

相关文章

  • 剑指 Offer 55 - II. 平衡二叉树(简单)
    题目:classSolution{public:intgetHeight(TreeNode*cur){//递归函数返回的是以当前节点为根节点的高度。if(!cur)return0;//空节点的高度为0intleftHeight=getHeight(cur->left);//取得左节点的高度if(leftHeight=......
  • 剑指Offer 21. 调整数组顺序使奇数位于偶数前面
    题目链接:剑指Offer21.调整数组顺序使奇数位于偶数前面题目描述:输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后半部分。解法思路:一、快慢指针法:快指针遍历整个数组,当遇到奇数时,将当前数与慢指针所指的数交换,最终......
  • 剑指Offer 18. 删除链表的节点
    题目链接:剑指Offer18.删除链表的节点题目描述:给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。返回删除后的链表的头节点。解法思路:由于包含删除第一个节点的情况,因此采用虚拟头节点,当遍历时找到待删除节点的前驱节点时,删除节点即可代码:/***Def......
  • 剑指Offer 17. 打印从1到最大的n位数
    题目链接:剑指Offer17.打印从1到最大的n位数题目描述:输入数字n,按顺序打印出从1到最大的n位十进制数。比如输入3,则打印出1、2、3一直到最大的3位数999。解法思路:利用上题中的代码,快速计算出10^n的值,然后依次将结果加到ans代码:funcprintNumbers(nint)[]int{......
  • 剑指Offer 15. 二进制中1的个数
    题目链接:剑指Offer15.二进制中1的个数题目描述:编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为'1'的个数(也被称为汉明重量).)。解法思路:思路一:num依次右移,判断每一次移动后最后一位是否是1,是的话,就ans++代码:func(numuint32)int{......
  • 剑指Offer 14- II. 剪绳子 II
    题目链接:剑指Offer14-II.剪绳子II题目描述:给你一根长度为n的绳子,请把绳子剪成整数长度的m段(m、n都是整数,n>1并且m>1),每段绳子的长度记为k[0],k[1]...k[m-1]。请问k[0]k[1]...*k[m-1]可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的......
  • Leetcode 454. 四数相加 II(4sum ii)
    题目链接给你四个整数数组nums1、nums2、nums3和nums4,数组长度都是n,请你计算有多少个元组(i,j,k,l)能满足:0<=i,j,k,l<nnums1[i]+nums2[j]+nums3[k]+nums4[l]==0示例1:输入:nums1=[1,2],nums2=[-2,-1],nums3=[-1,2],nums4=[0,2]输出:2......
  • [刷题记录Day14]Leetcode二叉树
    No.1题目前序遍历思路递归法代码publicvoidTraverse(TreeNodenode,List<Integer>list){if(node==null)return;list.add(node.val);//中Traverse(node.left,list);//左Traverse(node.right,list);//右}p......
  • [刷题记录Day15]Leetcode二叉树
    No.1题目二叉树的层序遍历思路使用队列关键点:1.每进入一层,层内的节点都被处理完成2.开始遍历层内的节点前,必须先记录该层的节点数量,不能访问到下一层的节点代码publicList<List<Integer>>levelOrder(TreeNoderoot){Queue<TreeNode>queue=newLinkedList......
  • [刷题记录Day17]Leetcode二叉树
    No.1题目平衡二叉树思路递归法在遍历中比较左右子树的高度差递归分析参数:当前传入节点。返回值:以当前传入节点为根节点的树的高度那么如何标记左右子树是否差值大于1呢?可以返回-1来标记已经不符合平衡树的规则了明确终止条件:递归的过程中依然是遇到空节点了为终止,返......