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

Same Tree

Problem (yeniden ifade)

İki ikili ağacın yapısal olarak özdeş ve aynı değerlere sahip olup olmadığını kontrol et.

Sezgi

İkisi null ise eşit; biri null değilse eşit değil; değerler eşitse children’da özyinele.

Yaklaşımlar

Özyinelemeli DFS

Doğrulanmadı

Zaman O(n)Alan O(h)

Fikir. isSame(p,q) = p.val==q.val and isSame sol and isSame sağ.

Yürüyüş. Özdeş şekil ve değerler → true.

Trade-off. DFS özyinelemesi vs BFS çift kuyruğu.

Çö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 isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  if (!p && !q) return true;
  if (!p || !q || p.val !== q.val) return false;
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

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 isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  if (!p && !q) return true;
  if (!p || !q || p.val !== q.val) return false;
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

Şablon bağlantısı

Tree DFS bool döndürür.

Yansıma

İkisi de null: true. Biri null: false. Değer ve iki çocuk aynı mı?
Ayna ağaç aynı değildir. Yapı aynı, değer farklı: false.
İki boş ağaç eşit.