树中两个结点的最低公共祖先

树是二叉搜索树

分析：
二叉搜索树都是排序过的，位于左子树的结点都比父结点小，而位于右子树的结点都比父结点大
从根结点开始和两个输入的结点进行比较，如果当前结点的值比两个结点的值都大，那么最低公共父结点一定是在当前结点的左子树中，于是下一步遍历当前结点的左子结点
如果当前结点的值比两个结点的值都小，那么最低公共结点一定是在当前结点的右子树中，于是下一步遍历当前结点的右子结点
这样在树中从上到下找到第一个在两个输入结点的值之间的结点，就是最低公共祖先

树不是二叉树但是有指向父结点的指针

分析：
如果树中每个节点都有指向父结点的指针，这个问题可以转换为求两个链表的第一个公共结点

树是一棵普通的树

分析：
从根结点开始遍历一棵树，每遍历到一个结点，判断两个输入结点是不是在它的子树中
如果在子树中，则分别遍历它的所有子结点，并判断两个输入结点是不是在它们子树中
这样从上到下一直找到的第一个结点，它自己的子树中同时包含两个输入的结点而它的子结点却没有，那么该结点就是最低公共祖先

优化：
两个链表保存从根节点到输入的两个结点的路径，然后把问题转换成两个链表的最后公共结点

class Node<Key extends Comparable<Key>, Vaule> {
    public Key key;
    public Vaule vaule;
    public Node left, right;

    public Node(Key key, Vaule vaule) {
        this.key = key;
        this.vaule = vaule;
    }
}

public class LastCommonParent {

    // 获取结点k的路径
    private boolean getNodePath(Node root, Node k, List<Node> path) {
        if (root.key.compareTo(k.key) == 0) {
            return true;
        }

        path.add(root);
        boolean found = false;
        if (!found && Optional.ofNullable(root.left).isPresent()) {
            found = getNodePath(root.left, k, path);
        }
        if (!found && Optional.ofNullable(root.right).isPresent()) {
            found = getNodePath(root.right, k, path);
        }
        if (!found) {
            path.remove(path.size() - 1);
        }
        return found;
    }

    // 公共子结点
    private Node getLastCommonNode(List<Node> m, List<Node> n) {
        if (Optional.ofNullable(m).isEmpty() || 
                Optional.ofNullable(n).isEmpty()) {
            throw new RuntimeException("list empty");
        }

        Node result = null;
        int count = 0;
        while (count < m.size() && count < n.size()) {
            if (m.get(count).key.compareTo(n.get(count).key) == 0) {
                result = m.get(count);
            }
            count++;
        }
        return result;
    }

    // true表示结点参数正确
    private boolean checkNode(Node... nodes) {
        boolean flag = true;
        for (Node node : nodes) {
            if (Optional.ofNullable(node).isEmpty()) {
                flag = false;
            }
        }
        return flag;
    }

    public Node getLastCommonParent(Node root, Node m, Node n) {
        if (!checkNode(root, m, n)) {
            throw new RuntimeException("node empty");
        }

        List<Node> ml = new LinkedList<>();
        List<Node> nl = new LinkedList<>();
        if (!getNodePath(root, m, ml) || !getNodePath(root, n, nl)) {
            throw new RuntimeException("invalid parameters");
        }

        return getLastCommonNode(ml, nl);
    }
}