Lowest Common Ancestor of a Binary Tree

Problem (yeniden ifade)

Bir ikili ağaç ve iki düğüm p ve q verildiğinde, en düşük ortak atalarını döndür (her ikisini de soy olarak barındıran en derin düğüm).

Sezgi

Sol biri, sağ diğeri bulursa bu düğüm LCA. İkisi bir taraftaysa o tarafı döndür.

Yaklaşımlar

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 lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode | null,
  q: TreeNode | null,
): TreeNode | null {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left ?? 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 lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode | null,
  q: TreeNode | null,
): TreeNode | null {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root;
  return left ?? right;
}

Şablon bağlantısı

Ağaç DFS alt ağaç tanığı döndürür.

Yansıma

• Post-order: sol ve sağ. İkisi de doluysa bu düğüm ata. Biri doluysa onu yukarı ver.
• p veya q düğümün kendisiyse onu döndür. Biri diğerinin altındaysa ata, bulunan düğümdür.
• p == q o düğüm. İkisi de ağaçta (garanti). Kök her zaman bir üst sınır.