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

Hardtree-dfs

Binary Tree Maximum Path Sum

Problem (yeniden ifade)

Yol, herhangi bir düğümden düğüme dizidir. Herhangi bir yoldaki düğüm değerlerinin maksimum toplamını döndür (en az bir düğüm).

Sezgi

Her düğümden ebeveyne sunulabilecek en iyi kazanç val + max(0, en iyi çocuk kazancı). Global cevap için her iki çocuğu da kullanan, düğümden geçen yolu da düşün.

Yaklaşımlar

Kazanç DFS + global en iyi

Tested only

Time O(n)Space O(h)

Fikir. dfs yukarı kazanç döndürür; globali leftGain+rightGain+val ile güncelle.

Adım adım. Negatif çocuklar max(0, …) ile atılır.

Trade-off’lar. Tek DFS; tümü negatif ağaçlara dikkat (en büyük düğümü seç).

Solution

export class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

export function maxPathSum(root: TreeNode | null): number {
  let best = -Infinity;
  const gain = (node: TreeNode | null): number => {
    if (!node) return 0;
    const left = Math.max(0, gain(node.left));
    const right = Math.max(0, gain(node.right));
    best = Math.max(best, node.val + left + right);
    return node.val + Math.max(left, right);
  };
  gain(root);
  return best;
}

export class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

export function maxPathSum(root: TreeNode | null): number {
  let best = -Infinity;
  const gain = (node: TreeNode | null): number => {
    if (!node) return 0;
    const left = Math.max(0, gain(node.left));
    const right = Math.max(0, gain(node.right));
    best = Math.max(best, node.val + left + right);
    return node.val + Math.max(left, right);
  };
  gain(root);
  return best;
}

Şablon bağlantısı

Ağaç DFS kazanç döndür + yan etki global.

Derinlemesine

Bir yol, her iki çocuğu da kullanarak bir düğümde bükülebilir; ancak ebeveyne dönen değer yalnızca bir tarafı (veya hiçbiri) içerebilir. Her DFS çağrısı:

leftGain = max(0, dfs(left)) ve benzer şekilde rightGain hesaplar (negatif kazançları atar).
Global en iyiyi val + leftGain + rightGain ile günceller (bu düğümden geçen yol).
val + max(leftGain, rightGain) döndürür (yukarı en iyi zincir).

Tümü negatif ağaçlar: en iyi yol en büyük tek düğümdür (0 kazanç çocuk eklemez).

Yansıma

90 saniye içinde hangi kalıp bunu verdi?
Standart şablondan ne değişti?
Mevcut çözümü ne bozar?