LeetCode 1483. 树节点的第 K 个祖先

Categories:

题目描述
思路分析
1. 解法一：倍增（推荐）
相似题目

题目描述

✅ 1483. 树节点的第 K 个祖先

思路分析

解法一：倍增（推荐）

核心思路：

预处理 up[i][j] 表示节点 i 的 2^j 级祖先。

查询时按二进制拆分 k，从高位到低位跳转。

若祖先不存在则返回 -1。

复杂度分析：

时间复杂度：O(n log n) 预处理，O(log n) 查询。

空间复杂度：O(n log n)。

class TreeAncestor {
    private final int[][] up;
    private final int maxLog;

    public TreeAncestor(int n, int[] parent) {
        int log = 1;
        while ((1 << log) <= n) {
            log++;
        }
        maxLog = log;
        up = new int[n][maxLog];

        for (int i = 0; i < n; i++) {
            up[i][0] = parent[i];
        }
        for (int j = 1; j < maxLog; j++) {
            for (int i = 0; i < n; i++) {
                int p = up[i][j - 1];
                up[i][j] = p == -1 ? -1 : up[p][j - 1];
            }
        }
    }

    public int getKthAncestor(int node, int k) {
        for (int j = 0; j < maxLog && node != -1; j++) {
            if (((k >> j) & 1) == 1) {
                node = up[node][j];
            }
        }
        return node;
    }
}

type TreeAncestor struct {
	up     [][]int
	maxLog int
}

func Constructor(n int, parent []int) TreeAncestor {
	log := 1
	for (1 << log) <= n {
		log++
	}

	up := make([][]int, n)
	for i := 0; i < n; i++ {
		up[i] = make([]int, log)
		up[i][0] = parent[i]
	}

	for j := 1; j < log; j++ {
		for i := 0; i < n; i++ {
			p := up[i][j-1]
			if p == -1 {
				up[i][j] = -1
			} else {
				up[i][j] = up[p][j-1]
			}
		}
	}

	return TreeAncestor{up: up, maxLog: log}
}

func (t *TreeAncestor) GetKthAncestor(node int, k int) int {
	for j := 0; j < t.maxLog && node != -1; j++ {
		if (k>>j)&1 == 1 {
			node = t.up[node][j]
		}
	}
	return node
}

相似题目

题目	难度	考察点
1483. 树节点的第 K 个祖先	困难	倍增
1135. 最低成本连通所有城市	中等	并查集
236. 二叉树的最近公共祖先	中等	树
235. 二叉搜索树的最近公共祖先	简单	BST
1319. 连通网络的操作次数	中等	并查集

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/44583981