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

Lowest Common Ancestor of a Binary Tree

Problem (restated)

Given a binary tree and two nodes p and q, return their lowest common ancestor (deepest node that has both as descendants).

Intuition

If left finds one and right finds the other, this node is LCA. If both under one side, return that side.

Approaches

Post-order LCA

Tested only

Time O(n)Space O(h)

Idea. dfs: if node is p or q or null return node; combine left/right results.

Walkthrough. p and q on different sides of root → root is LCA.

Trade-offs. Recursive post-order is standard; parent pointers need extra structure.

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 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;
}

Template connection

Tree DFS return subtree witness.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?