[Algo] 127. Lowest Common Ancestor II

/**
 * public class TreeNodeP {
 *   public int key;
 *   public TreeNodeP left;
 *   public TreeNodeP right;
 *   public TreeNodeP parent;
 *   public TreeNodeP(int key, TreeNodeP parent) {
 *     this.key = key;
 *     this.parent = parent;
 *   }
 * }
 */
public class Solution {
  public TreeNodeP lowestCommonAncestor(TreeNodeP one, TreeNodeP two) {
    // Write your solution here.
    int aLen = getHeight(one);
    int bLen = getHeight(two);
    if (aLen >= bLen) {
      return getLCANode(aLen - bLen, one, two);
    } else {
      return getLCANode(bLen - aLen, two, one);
    }
  }

  private int getHeight(TreeNodeP node) {
    int len = 0;
    while (node != null) {
      node = node.parent;
      len += 1;
    }
    return len;
  }

  private TreeNodeP getLCANode(int diff, TreeNodeP node, TreeNodeP other) {
    while (diff > 0) {
      node = node.parent;
      diff -= 1;
    }
    while (node != other) {
      node = node.parent;
      other = other.parent;
    }
    return node;
  }
}