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

Mediumtree-dfs

Validate Binary Search Tree

Problem (yeniden ifade)

Bir ikili ağacın geçerli BST olup olmadığını belirle: her düğüm sol alt ağacındaki her şeyden katı büyük, sağdakinden katı küçük.

Sezgi

Her kenardan (low, high) geçir. Düğüm değeri açık aralığın içinde olmalı.

Yaklaşımlar

Sınırlı DFS

Doğrulanmadı

Zaman O(n)Alan O(h)

Fikir. isValid(node, low, high): null ok; low < val < high; sola (low,val) ve sağa (val,high) özyinele.

Yürüyüş. Klasik geçersiz: kök 5, sağ 4 (4, 5’ten > değil).

Trade-off. Sınırlı DFS temizdir; inorder katı artan olmalı.

Çö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 isValidBST(root: TreeNode | null): boolean {
  const go = (node: TreeNode | null, low: number, high: number): boolean => {
    if (!node) return true;
    if (node.val <= low || node.val >= high) return false;
    return go(node.left, low, node.val) && go(node.right, node.val, high);
  };
  return go(root, -Infinity, Infinity);
}

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 isValidBST(root: TreeNode | null): boolean {
  const go = (node: TreeNode | null, low: number, high: number): boolean => {
    if (!node) return true;
    if (node.val <= low || node.val >= high) return false;
    return go(node.left, low, node.val) && go(node.right, node.val, high);
  };
  return go(root, -Infinity, Infinity);
}

Şablon bağlantısı

Aşağı state geçiren tree DFS.

Yansıma

Yalnız ebeveyn yetmez. Sağ alttaki küçük değer kökten de küçük olabilir. Aralık (low, high) iner.
Eşitlik BST değil. int sınırındaki değer: low/high’ı null tut, MinValue’yu sınır sanma.
Tek düğüm true. Boş ağaç true.