P138 二叉树中节点的最近公共祖先

描述#

这个题目说的是，给你一棵二叉树以及树中两个节点，你要找到这两个节点的最近公共祖先，然后将它返回。

比如说，给你的二叉树是：
  1
/   \

2     3
/ \     

4   5     6
节点 4 和 5 的最近公共祖先是节点 2；
节点 5 和 6 的最近公共祖先是节点 1；
节点 1 和 6 的最近公共祖先也是节点 1。

代码#

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  private boolean search(TreeNode root, TreeNode node, List<TreeNode> path) {
    if (root == null) return false;
    path.add(root);
    if (root == node) return true;
    boolean ret = search(root.left, node, path) || search(root.right, node, path);
    if (ret) return true;
    path.remove(path.size()-1);
    return false;
  }

  // Time: O(n), Space: O(n)
  public TreeNode lcaWithPath(TreeNode root, TreeNode p, TreeNode q) {
    List<TreeNode> ppath = new ArrayList<>();
    List<TreeNode> qpath = new ArrayList<>();
    search(root, p, ppath);
    search(root, q, qpath);
    int i = 0, len = Math.min(ppath.size(), qpath.size());
    while (i < len && ppath.get(i) == qpath.get(i)) ++i;
    return ppath.get(i-1);
  }

  // Time: O(n), Space: O(n)
  public TreeNode lcaExtend(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lcaExtend(root.left, p, q);
    TreeNode right = lcaExtend(root.right, p, q);
    if (left != null && right != null) return root;
    else if (left != null) return left;
    else return right;
  }

}