Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumtopological-sort

Minimum Height Trees

Problem (yeniden ifade)

n düğümlü yönsüz ağaç. Köklenmiş ağacın yüksekliğini en aza indiren tüm kökleri döndür (1 veya 2 merkez).

Sezgi

Yaprakları (derece 1) tekrar tekrar kaldır. Son kalan 1-2 düğüm merkez / MHT kökleridir.

Yaklaşımlar

Yaprakları soyarak merkezlere

Doğrulanmadı

Zaman O(n)Alan O(n)

Fikir. ≤2 düğüm kalana kadar Kahn tarzı katman soyma.

Adım adım. n=4, edges=[[1,0],[1,2],[1,3]] → [1].

Trade-off’lar. Çap orta noktaları aynı cevabı verir; yaprak soyma kodlaması daha basit.

Çözüm

export function findMinHeightTrees(n: number, edges: number[][]): number[] {
  if (n === 1) return [0];
  const g: number[][] = Array.from({ length: n }, () => []);
  const deg = Array(n).fill(0);
  for (const e of edges) {
    g[e[0]!]!.push(e[1]!);
    g[e[1]!]!.push(e[0]!);
    deg[e[0]!]!++;
    deg[e[1]!]!++;
  }
  let q: number[] = [];
  for (let i = 0; i < n; i++) if (deg[i] === 1) q.push(i);
  let remain = n;
  while (remain > 2) {
    const next: number[] = [];
    remain -= q.length;
    for (const u of q) {
      for (const v of g[u]!) {
        if (--deg[v]! === 1) next.push(v);
      }
    }
    q = next;
  }
  return q;
}

export function findMinHeightTrees(n: number, edges: number[][]): number[] {
  if (n === 1) return [0];
  const g: number[][] = Array.from({ length: n }, () => []);
  const deg = Array(n).fill(0);
  for (const e of edges) {
    g[e[0]!]!.push(e[1]!);
    g[e[1]!]!.push(e[0]!);
    deg[e[0]!]!++;
    deg[e[1]!]!++;
  }
  let q: number[] = [];
  for (let i = 0; i < n; i++) if (deg[i] === 1) q.push(i);
  let remain = n;
  while (remain > 2) {
    const next: number[] = [];
    remain -= q.length;
    for (const u of q) {
      for (const v of g[u]!) {
        if (--deg[v]! === 1) next.push(v);
      }
    }
    q = next;
  }
  return q;
}

Şablon bağlantısı

Katmanlı yaprak kaldırma (ağaçlarda topo benzeri).

Yansıma

Yaprakları soy, derece 1. Son turda 1 veya 2 düğüm kalır: merkezler. n ≤ 2 hepsi cevaptır.
Ağaç garantisi, döngü yok. Her tur yalnız o anki yaprakları kes; yeni yaprak aynı turda kesilmez.
Zincirin ortası 1 veya 2 düğüm. Yıldızda merkez kalır.