題目

題目

思路

遞歸

• 最近公共祖先x滿足：
  x的左右子樹分別包含p節(jié)點(diǎn)或q節(jié)點(diǎn)，或者x恰好是p節(jié)點(diǎn)或q節(jié)點(diǎn)且它的左子樹或右子樹有一個包含了另一個節(jié)點(diǎn)

class Solution {
  private TreeNode ans = null;
  private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) {
      return false;
    }
    boolean lChild = dfs(root.left, p, q);
    if (lChild && (root == p || root ==q)) {
      ans = root;
      return true;
    }
    boolean rChild = dfs(root.right, p ,q);
    if (rChild && (root == p || root ==q)) {
      ans = root;
      return true;
    }
    if (lChild && rChild) {
      ans = root;
      return true;
    }
    return lChild || rChild || root == p || root ==q;
  }
  
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    dfs(root, p, q);
    return ans;
  }
}

存儲父節(jié)點(diǎn)

遍歷二叉樹使用哈希表存儲所有節(jié)點(diǎn)的父節(jié)點(diǎn)，利用父節(jié)點(diǎn)信息從p節(jié)點(diǎn)開始不斷往上跳，并記錄已經(jīng)訪問過的節(jié)點(diǎn)，再從q節(jié)點(diǎn)開始不斷往上跳，得到最先碰到的已經(jīng)訪問過的節(jié)點(diǎn)。

class Solution {
  // <child, parent>
  Map<TreeNode, TreeNode> parent = new HashMap<>();
  Set<TreeNode> visited = new HashSet<>();
  public void dfs(TreeNode root) {
    if (root.left != null) {
      parent.put(root.left, root);
      dfs(root.left);
    }
    if (root.right != null) {
      parent.put(root.right, root);
      dfs(root.right);
    }
  }

  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    dfs(root);
    while (p != null) {
      visited.add(p);
      p = parent.get(p);
    }
    while (q != null) {
      if (visited.contains(q)) {
        return q;
      }
      q = parent.get(q);
    }
    return null;
  }
}