Given two nodes in a binary tree (with parent pointer available), find their lowest common ancestor.

Assumptions

• There is parentpointer for the nodes in the binary tree

• The given two nodes are not guaranteed to be in the binary tree

Examples

    5

  /   \

 9     12

/ \ \

2 3 14

The lowest common ancestor of 2 and 14 is 5

The lowest common ancestor of 2 and 9 is 9

The lowest common ancestor of 2 and 8 is null (8 is not in the tree)

Solution 1: 用hashset记录出现过的node

  public TreeNodeP lowestCommonAncestor(TreeNodeP one, TreeNodeP two) {
    Set<TreeNodeP> set = new HashSet<>();
    while (one != null && two != null) {
      if (set.contains(one)) {
        return one;
      }
      set.add(one);
      if (set.contains(two)) {
        return two;
      }
      set.add(two);
      one = one.parent;
      two = two.parent;
    }
    while (one != null) {
      if (set.contains(one)) {
        return one;
      }
      one = one.parent;
    }
    while (two != null) {
      if (set.contains(two)) {
        return two;
      }
      two = two.parent;
    }

    return null;
  }

Solution 2: 先求2条path的长度，再把长的那条移到与短的相同位置后，求2 linkedlist的共同点