题目

题目

思路

递归

• 最近公共祖先x满足：
  x的左右子树分别包含p节点或q节点，或者x恰好是p节点或q节点且它的左子树或右子树有一个包含了另一个节点

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

存储父节点

遍历二叉树使用哈希表存储所有节点的父节点，利用父节点信息从p节点开始不断往上跳，并记录已经访问过的节点，再从q节点开始不断往上跳，得到最先碰到的已经访问过的节点。

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