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

Easytree-dfs

Balanced Binary Tree

Problem (yeniden ifade)

Yükseklik dengeli bir ağaçta her düğümde |leftHeight, rightHeight| ≤ 1. Ağacın dengeli olup olmadığını kontrol et.

Sezgi

Her alt ağaçtan yükseklik dön; bir taraf dengesizse veya yükseklikler >1 fark ederse sentinel yukarı taşı.

Yaklaşımlar

Yükseklik + bayrak DFS

Doğrulanmadı

Zaman O(n)Alan O(h)

Fikir. height(node): çocuk -1 dönerse veya |hl-hr|>1 ise -1; değilse 1+max.

Yürüyüş. Küçük mükemmel ağaçlar tamam; bir tarafta uzun zincir başarısız.

Trade-off. Tek DFS O(n); naif yükseklik yeniden hesaplama O(n²).

Çözüm

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 isBalanced(root: TreeNode | null): boolean {
  const height = (node: TreeNode | null): number => {
    if (!node) return 0;
    const hl = height(node.left);
    if (hl < 0) return -1;
    const hr = height(node.right);
    if (hr < 0) return -1;
    if (Math.abs(hl - hr) > 1) return -1;
    return 1 + Math.max(hl, hr);
  };
  return height(root) >= 0;
}

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 isBalanced(root: TreeNode | null): boolean {
  const height = (node: TreeNode | null): number => {
    if (!node) return 0;
    const hl = height(node.left);
    if (hl < 0) return -1;
    const hr = height(node.right);
    if (hr < 0) return -1;
    if (Math.abs(hl - hr) > 1) return -1;
    return 1 + Math.max(hl, hr);
  };
  return height(root) >= 0;
}

Şablon bağlantısı

Tree DFS çok alanlı dönüş.

Yansıma

Her düğümde |sol − sağ| ≤ 1. Kök dengeli görünüp alt ağaç dengesiz olabilir; bunu yükseklikle yukarı taşı.
Dengesiz alt ağaç −1 dönerse kardeşi gezmeden çık. Yaprak dengeli.
Tek çocuklu uzun zincir dengesiz. Boş ağaç dengeli.