2023-06-12 LeetCode每日一题(树节点的第 K 个祖先)

这篇具有很好参考价值的文章主要介绍了2023-06-12 LeetCode每日一题(树节点的第 K 个祖先)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

2023-06-12每日一题

一、题目编号

1483. 树节点的第 K 个祖先

二、题目链接

点击跳转到题目位置

三、题目描述

给你一棵树,树上有 n 个节点,按从 0 到 n-1 编号。树以父节点数组的形式给出,其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。

树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。

实现 TreeAncestor 类:

  • TreeAncestor(int n, int[] parent) 对树和父数组中的节点数初始化对象。
  • getKthAncestor(int node, int k) 返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点,返回 -1 。

提示:文章来源地址https://www.toymoban.com/news/detail-479981.html

  • 1 <= k <= n <= 5 * 104
  • parent[0] == -1 表示编号为 0 的节点是根节点。
  • 对于所有的 0 < i < n ,0 <= parent[i] < n 总成立
  • 0 <= node < n
  • 至多查询 5 * 104

四、解题代码

class TreeAncestor {
public:
    const int Log = 16;
    vector<vector<int>> ancestors;

    TreeAncestor(int n, vector<int>& parent) {
        ancestors = vector<vector<int>>(n, vector<int>(Log, -1));
        for (int i = 0; i < n; ++i) {
            ancestors[i][0] = parent[i];
        }
        for (int j = 1; j < Log; ++j) {
            for (int i = 0; i < n; i++) {
                if (ancestors[i][j - 1] != -1) {
                    ancestors[i][j] = ancestors[ancestors[i][j - 1]][j - 1];
                }
            }
        }           
    }
    
    int getKthAncestor(int node, int k) {
        for (int j = 0; j < Log; j++) {
            if ((k >> j) & 1) {
                node = ancestors[node][j];
                if (node == -1) {
                    return -1;
                }
            }
        }
        return node;
    }
};

/**
 * Your TreeAncestor object will be instantiated and called as such:
 * TreeAncestor* obj = new TreeAncestor(n, parent);
 * int param_1 = obj->getKthAncestor(node,k);
 */

五、解题思路

到了这里,关于2023-06-12 LeetCode每日一题(树节点的第 K 个祖先)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 2023-06-16 LeetCode每日一题(并行课程 II)

    点击跳转到题目位置 给你一个整数 n 表示某所大学里课程的数目,编号为 1 到 n ,数组 relations 中, relations[i] = [xi, yi] 表示一个先修课的关系,也就是课程 xi 必须在课程 yi 之前上。同时你还有一个整数 k 。 在一个学期中,你 最多 可以同时上 k 门课,前提是这些课的先修课

    2024年02月09日
    浏览(46)
  • 2023-06-17 LeetCode每日一题(分割圆的最少切割次数)

    点击跳转到题目位置 圆内一个 有效切割 ,符合以下二者之一: 该切割是两个端点在圆上的线段,且该线段经过圆心。 该切割是一端在圆心另一端在圆上的线段。 一些有效和无效的切割如下图所示。 给你一个整数 n ,请你返回将圆切割成相等的 n 等分的 最少 切割次数。

    2024年02月09日
    浏览(53)
  • 2023-06-14 LeetCode每日一题(二进制字符串前缀一致的次数)

    点击跳转到题目位置 给你一个长度为 n 、下标从 1 开始的二进制字符串,所有位最开始都是 0 。我们会按步翻转该二进制字符串的所有位(即,将 0 变为 1)。 给你一个下标从 1 开始的整数数组 flips ,其中 flips[i] 表示对应下标 i 的位将会在第 i 步翻转。 二进制字符串 前缀

    2024年02月08日
    浏览(54)
  • 2023-06-02 LeetCode每日一题(统计范围内的元音字符串数)

    点击跳转到题目位置 给你一个下标从 0 开始的字符串数组 words 以及一个二维整数数组 queries 。 每个查询 queries[i] = [li, ri] 会要求我们统计在 words 中下标在 li 到 ri 范围内( 包含 这两个值)并且以元音开头和结尾的字符串的数目。 返回一个整数数组,其中数组的第 i 个元素

    2024年02月07日
    浏览(53)
  • 2023-08-12 LeetCode每日一题(合并 K 个升序链表)

    点击跳转到题目位置 给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。 示例 1: 示例 2: 示例 3:

    2024年02月13日
    浏览(41)
  • 2023-08-25 LeetCode每日一题(统计二叉树中好节点的数目)

    点击跳转到题目位置 给你一棵根为 root 的二叉树,请你返回二叉树中好节点的数目。 「好节点」X 定义为:从根到该节点 X 所经过的节点中,没有任何节点的值大于 X 的值。 示例 1: 示例 2: 示例 3: 提示: 二叉树中节点数目范围是 [1, 10 5 ] 。 每个节点权值的范围是 [-10

    2024年02月11日
    浏览(36)
  • Leetcode每日一题:1448. 统计二叉树中好节点的数目(2023.8.25 C++)

    目录 1448. 统计二叉树中好节点的数目 题目描述: 实现代码与解析: dfs 原理思路:         给你一棵根为  root  的二叉树,请你返回二叉树中好节点的数目。 「好节点」X 定义为:从根到该节点 X 所经过的节点中,没有任何节点的值大于 X 的值。 示例 1: 示例 2: 示例

    2024年02月11日
    浏览(39)
  • 236. 二叉树的最近公共祖先 ——【Leetcode每日一题】

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

    2023年04月26日
    浏览(36)
  • LeetCode-1483. 树节点的第 K 个祖先【树 深度优先搜索 广度优先搜索 设计 二分查找 动态规划】

    给你一棵树,树上有 n 个节点,按从 0 到 n-1 编号。树以父节点数组的形式给出,其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。 树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。 实现 TreeAncestor 类: TreeAncestor(int n, int[] parent) 对树和父

    2024年04月16日
    浏览(39)
  • 每日一题——LeetCode1154.一年中的第几天

    方法一 列举法: 用一个数组把每个月份的天数都列举出来 判断闰年,是闰年2月份有29天 循环对当前月份之前的月份天数求和 加上当天月份的天数 消耗时间和内存情况:

    2024年02月02日
    浏览(41)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包