樹中兩個結(jié)點(diǎn)的最低公共祖先

樹是二叉搜索樹

分析：
二叉搜索樹都是排序過的玛追，位于左子樹的結(jié)點(diǎn)都比父結(jié)點(diǎn)小，而位于右子樹的結(jié)點(diǎn)都比父結(jié)點(diǎn)大
從根結(jié)點(diǎn)開始和兩個輸入的結(jié)點(diǎn)進(jìn)行比較胳施，如果當(dāng)前結(jié)點(diǎn)的值比兩個結(jié)點(diǎn)的值都大奇适，那么最低公共父結(jié)點(diǎn)一定是在當(dāng)前結(jié)點(diǎn)的左子樹中，于是下一步遍歷當(dāng)前結(jié)點(diǎn)的左子結(jié)點(diǎn)
如果當(dāng)前結(jié)點(diǎn)的值比兩個結(jié)點(diǎn)的值都小叹俏，那么最低公共結(jié)點(diǎn)一定是在當(dāng)前結(jié)點(diǎn)的右子樹中妻枕，于是下一步遍歷當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)
這樣在樹中從上到下找到第一個在兩個輸入結(jié)點(diǎn)的值之間的結(jié)點(diǎn)，就是最低公共祖先

樹不是二叉樹但是有指向父結(jié)點(diǎn)的指針

分析：
如果樹中每個節(jié)點(diǎn)都有指向父結(jié)點(diǎn)的指針，這個問題可以轉(zhuǎn)換為求兩個鏈表的第一個公共結(jié)點(diǎn)

樹是一棵普通的樹

分析：
從根結(jié)點(diǎn)開始遍歷一棵樹屡谐，每遍歷到一個結(jié)點(diǎn)述么，判斷兩個輸入結(jié)點(diǎn)是不是在它的子樹中
如果在子樹中，則分別遍歷它的所有子結(jié)點(diǎn)愕掏，并判斷兩個輸入結(jié)點(diǎn)是不是在它們子樹中
這樣從上到下一直找到的第一個結(jié)點(diǎn)度秘，它自己的子樹中同時包含兩個輸入的結(jié)點(diǎn)而它的子結(jié)點(diǎn)卻沒有，那么該結(jié)點(diǎn)就是最低公共祖先

優(yōu)化：
兩個鏈表保存從根節(jié)點(diǎn)到輸入的兩個結(jié)點(diǎn)的路徑饵撑，然后把問題轉(zhuǎn)換成兩個鏈表的最后公共結(jié)點(diǎn)

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 {

    // 獲取結(jié)點(diǎn)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;
    }

    // 公共子結(jié)點(diǎn)
    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表示結(jié)點(diǎn)參數(shù)正確
    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);
    }
}