LeetCode每日一题:1123. 最深叶节点的最近公共祖先(2023.9.6 C++)

这篇具有很好参考价值的文章主要介绍了LeetCode每日一题:1123. 最深叶节点的最近公共祖先(2023.9.6 C++)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

1123. 最深叶节点的最近公共祖先

题目描述:

实现代码与解析:

dfs

原理思路:


1123. 最深叶节点的最近公共祖先

题目描述:

        给你一个有根节点 root 的二叉树,返回它 最深的叶节点的最近公共祖先 。

回想一下:

  • 叶节点 是二叉树中没有子节点的节点
  • 树的根节点的 深度 为 0,如果某一节点的深度为 d,那它的子节点的深度就是 d+1
  • 如果我们假定 A 是一组节点 S 的 最近公共祖先S 中的每个节点都在以 A 为根节点的子树中,且 A 的深度达到此条件下可能的最大值。

示例 1:

LeetCode每日一题:1123. 最深叶节点的最近公共祖先(2023.9.6 C++),LeetCode,leetcode,c++,算法

输入:root = [3,5,1,6,2,0,8,null,null,7,4]
输出:[2,7,4]
解释:我们返回值为 2 的节点,在图中用黄色标记。
在图中用蓝色标记的是树的最深的节点。
注意,节点 6、0 和 8 也是叶节点,但是它们的深度是 2 ,而节点 7 和 4 的深度是 3 。

示例 2:

输入:root = [1]
输出:[1]
解释:根节点是树中最深的节点,它是它本身的最近公共祖先。

示例 3:

输入:root = [0,1,3,null,2]
输出:[2]
解释:树中最深的叶节点是 2 ,最近公共祖先是它自己。

提示:

  • 树中的节点数将在 [1, 1000] 的范围内。
  • 0 <= Node.val <= 1000
  • 每个节点的值都是 独一无二 的。

实现代码与解析:

dfs

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int dfs(TreeNode* cur) // 获取当前节点可到达的最大深度
    {
        if (cur == NULL) return 0;
        int l = dfs(cur->left);
        int r = dfs(cur->right);

        return max(l, r) + 1;
    }
    TreeNode* lcaDeepestLeaves(TreeNode* root) {

        int dl = dfs(root->left); // 左
        int dr = dfs(root->right); // 右
        if (dl == dr) return root;
        else if (dl > dr) return lcaDeepestLeaves(root->left);
        else return lcaDeepestLeaves(root->right);
    }
};

原理思路:

        只要读懂题目就很好写了。

        题目含义:其实就是返回两个最深的节点的最近的公共祖先。

        每次递归向深度大的方向递归,若深度相同,说明找到了该节点,返回即可。最深的节点如果只要一个,那就是他自己。文章来源地址https://www.toymoban.com/news/detail-698716.html

到了这里,关于LeetCode每日一题:1123. 最深叶节点的最近公共祖先(2023.9.6 C++)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

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

            这道题是道面试高频题,并且有点抽象。         首先确定终止条件。如果根节点为空,或者其中一个节点是根节点本身(即 p == root 或 q == root ),那么根节点就是它们的最低共同祖先,因此我们直接返回根节点 root 。          接下来,递归调用 lowestComm

    2024年02月15日
    浏览(38)
  • leetcode热题100. 二叉树的最近公共祖先

    Problem: 236. 二叉树的最近公共祖先 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先

    2024年01月19日
    浏览(42)
  • (链表) 剑指 Offer 52. 两个链表的第一个公共节点 ——【Leetcode每日一题】

    难度:简单 输入两个链表,找出它们的第一个公共节点。 如下面的两个链表: 在节点 c1 开始相交。 示例 1: 输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出:Reference of the node with value = 8 输入解释:相交节点的值为 8 (注意,如果两个列表相交则

    2024年02月15日
    浏览(53)
  • LeetCode235. 二叉搜索树的最近公共祖先

    235. 二叉搜索树的最近公共祖先 一、题目 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大( 一个节点也可以是

    2024年02月12日
    浏览(37)
  • LeetCode(力扣)236. 二叉树的最近公共祖先Python

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

    2024年02月10日
    浏览(38)
  • 【LeetCode75】第三十八题 二叉树的最近公共祖先

    目录 题目: 示例: 分析: 代码:  给我们一棵二叉树,然后给我们pq两个节点,让我们找出二叉树中它们俩的最近的公共祖先。 那么什么样的节点是它们俩的最近的公共祖先呢,是有两种情况,第一种情况的pq两个节点都在同一条路径上,像下图这样:  那这时pq的最近公

    2024年02月11日
    浏览(36)
  • 【算法与数据结构】236、LeetCode二叉树的最近公共祖先

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 : 根据定义,最近祖先节点需要遍历节点的左右子树,然后才能知道是否为最近祖先节点。 那么这种需求是先遍历左右节点,然后遍历中间节点,属于左右中的后序遍历模式 。因此

    2024年02月09日
    浏览(39)
  • C/C++每日一练(20230515) 区间和的个数、BST最近公共祖先、最接近元素

    目录 1. 区间和的个数  🌟🌟🌟 2. 二叉搜索树的最近公共祖先  🌟 3. 找最接近元素  🌟🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 给你一个整数数组  nums  以及两个整数  lower  和  upper  。求数组中,值

    2024年02月04日
    浏览(42)
  • LeetCode_二叉搜索树_中等_236.二叉搜索树的最近公共祖先

    给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” 例如,给定如下二叉搜

    2023年04月10日
    浏览(38)
  • Java LeetCode篇-二叉搜索树经典解法(实现:二叉搜索树的最近公共祖先、根据前序遍历建树等)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍    文章目录         1.0 判断合法         1.1 使用遍历方式实现验证二叉搜索树         1.2 使用递归方式实现验证二叉搜索树         2.0 求范围和         2.1 使用非递归实现二叉搜索树的范围和

    2024年02月03日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包