首页 > 其他分享 >236. 二叉树的最近公共祖先(leetcode)

236. 二叉树的最近公共祖先(leetcode)

时间:2024-05-08 22:56:15浏览次数:22  
标签:right TreeNode 祖先 二叉树 公共 236 root leetcode left

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/

要点是后序遍历,这样就可以从树底开始搜索,寻找最近公共祖先

class Solution {
public:
    // 返回的是最近公共祖先,若返回null则说明没有
    TreeNode* lowestCommonAncestor(TreeNode* root,TreeNode* p,TreeNode* q)
    {
        // 后序
        // 找到一个节点或者到达树底
        if(root==nullptr || root==p || root==q)return root;
        // 搜索左右子树是否有对应节点,有则返回最近公共最先节点,没有则返回空
        TreeNode* left = lowestCommonAncestor(root->left,p,q);
        TreeNode* right = lowestCommonAncestor(root->right,p,q);
        // 左右子树都有对应节点,意味着此时root节点为最近公共祖先
        if(left && right)return root;
        // 右有左没有,此时right被递归赋值了,就是最近公共祖先
        if(left==nullptr)return right;
        // 左有右没有,此时left被递归赋值了,就是最近公共祖先
        return left;
    }
};

标签:right,TreeNode,祖先,二叉树,公共,236,root,leetcode,left
From: https://www.cnblogs.com/lxl-233/p/18181098

相关文章

  • leetCode 001.两数之和
    给定一个整数数组nums和一个整数目标值target,请你在该数组中找出和为目标值target的那两个整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。示例1:输入:nums=[2,7,11,15],ta......
  • LeetCode 049. 字母异位词分组
    给你一个字符串数组,请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的所有字母得到的一个新单词。示例1:输入:strs=["eat","tea","tan","ate","nat","bat"]输出:[["bat"],["nat","tan"],["......
  • leetCode 128. 最长连续序列
    给定一个未排序的整数数组nums,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。请你设计并实现时间复杂度为O(n)的算法解决此问题。示例1:输入:nums=[100,4,200,1,3,2]输出:4解释:最长数字连续序列是[1,2,3,4]。它的长度为4。示例2:输入:nums=[0,3,7,......
  • Leetcode --- 203. 移除链表元素
    题目描述给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val==val 的节点,并返回 新的头节点 。示例1: 示例输入:head=[1,2,6,3,4,5,6],val=6输出:[1,2,3,4,5]输入:head=[7,7,7,7],val=7输出:[]参考实现方式1、使用递归实现......
  • [LeetCode] 2487. Remove Nodes From Linked List
    Youaregiventheheadofalinkedlist.Removeeverynodewhichhasanodewithagreatervalueanywheretotherightsideofit.Returntheheadofthemodifiedlinkedlist.Example1:Input:head=[5,2,13,3,8]Output:[13,8]Explanation:Thenodesth......
  • LeetCode 2060. Check if an Original String Exists Given Two Encoded Strings
    原题链接在这里:https://leetcode.com/problems/check-if-an-original-string-exists-given-two-encoded-strings/description/题目:Anoriginalstring,consistingoflowercaseEnglishletters,canbeencodedbythefollowingsteps:Arbitrarily split itintoa sequ......
  • 如何根据二叉树遍历结果快速绘制二叉树
    一、已知前序遍历和中序遍历(1)前序遍历(根结点--->左子树--->右子树)ABDGHCEIF(2)中序遍历(左子树--->根结点--->右子树)GDHBAEICF注意:在最后连接二叉树时,注意先完玩左子树,再连右子树二、已知前后序遍历和中序遍历(1)后序遍历(左子树--->右......
  • 【LeetCode 2008】出租车的最大盈利
    题目描述原题链接:LeetCode.2008出租车的最大盈利解题思路按二分查找和动态规划标签搜题库翻到的题目,相当于揣着俩提示来做题了;总体来说可以从下车地点编号或者前i个行程这两种维度进行DP;思路一:将行程按照下车地点编号由小到大排序;dp[i]定义为排序后在[0...i]行程中选......
  • 二叉树
    二叉树特点:每个结点最多有两颗子树,并且子树有左右之分。把一个结点拥有的子树的数量称为结点 的度,度为0的结点称为叶子结点,度不为0称为分支结点,树的最大层数称为树的深度性质:1.非空二叉树中的叶子结点数量等于双分支结点数量+12.二叉树的第i层上最多有2^(i-1)(i>=1)......
  • 二叉树进阶:二叉搜索树、平衡二叉树、KD树(实现KNN算法的快速寻找k个邻居)
    二叉搜索树二叉搜索树又称为二叉排序树、二叉查找树。请记住,本篇所介绍的所有树,都是二叉搜索树,也就是说都用到了二分查找的思想。二叉搜索树的特征:每个结点的左结点都小于结点本身,右结点都大于结点本身。用中序遍历来遍历一棵二叉搜索树,结果必然是有序的。时间复杂度很低......