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

題目：求樹中兩個(gè)結(jié)點(diǎn)的最低公共祖先，此樹不是二叉樹，并且沒有指向父節(jié)點(diǎn)的指針。

樹的結(jié)點(diǎn)定義

private static class TreeNode {
    int val;
    List<TreeNode> children = new LinkedList<>();
    public TreeNode() {
    }
    public TreeNode(int val) {
        this.val = val;
    }
    @Override
    public String toString() {
        return  val + "";
    }
}

題目解析

假設(shè)還是輸入結(jié)點(diǎn) F 和 H。

http://wiki.jikexueyuan.com/project/for-offer/images/67.png" alt="" />

我們首先得到一條從根結(jié)點(diǎn)到樹中某一結(jié)點(diǎn)的路徑，這就要求在遍歷的時(shí)候，有一個(gè)輔助內(nèi)存來保存路徑。比如我們用前序遍歷的方法來得到從根結(jié)點(diǎn)到 H 的路徑的過程是這樣的：（ 1 ）遍歷到 A，把 A 存放到路徑中去，路徑中只有一個(gè)結(jié)點(diǎn) A；( 2 ）遍歷到 B，把 B 存到路徑中去，此時(shí)路徑為 A->B; ( 3 ）遍歷到 D，把 D 存放到路徑中去，此，時(shí)路徑為 A->B->D；( 4 ）：遍歷到 F，把 F 存放到路徑中去，此時(shí)路徑為 A->B->D->F；( 5) F 已經(jīng)沒有子結(jié)點(diǎn)了，因此這條路徑不可能到這結(jié)點(diǎn) H。 把 F 從路徑中刪除，變成 A->B->D; ( 6 ）遍歷 G。 和結(jié)點(diǎn)F 一樣，這條路徑也不能到達(dá) H。邊歷完 G 之后，路徑仍然是 A->B->D； ( 7 ）由于 D 的所有子結(jié)點(diǎn)都遍歷過了，不可能到這結(jié)點(diǎn) H，因此 D 不在從 A 到 H 的路徑中，把 D 從路徑中刪除，變成 A->B； ( 8 ）遙歷 E，把 E 加入到路徑中，此時(shí)路徑變成 A->B->E， ( 9 ）遍歷 H，已經(jīng)到達(dá)目標(biāo)給點(diǎn)， A->B->E 就是從根結(jié)點(diǎn)開始到達(dá) H 必須經(jīng)過的路徑。

同樣，我們也可以得到從根結(jié)點(diǎn)開始到達(dá) F 必須經(jīng)過的路徑是 A->B。接著，我們求出這兩個(gè)路徑的最后公共結(jié)點(diǎn)，也就是 B。B 這個(gè)結(jié)點(diǎn)也是 F 和 H 的最低公共祖先．

為了得到從根結(jié)點(diǎn)開始到輸入的兩個(gè)結(jié)點(diǎn)的兩條路徑，需要追歷兩次樹，每邊歷一次的時(shí)間復(fù)雜度是 O(n）。得到的兩條路徑的長(zhǎng)度在最差情況時(shí)是 0（通常情況丁兩條路徑的長(zhǎng)度是 O(logn)。

注意：可以在只遍歷樹一次就找到兩個(gè)結(jié)點(diǎn)的路徑，這部分留給讀者自己去完成。

代碼實(shí)現(xiàn)

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
public class Test50 {
    /**
     * 樹的結(jié)點(diǎn)定義
     */
    private static class TreeNode {
        int val;
        List<TreeNode> children = new LinkedList<>();
        public TreeNode() {
        }
        public TreeNode(int val) {
            this.val = val;
        }
        @Override
        public String toString() {
            return val + "";
        }
    }
    /**
     * 找結(jié)點(diǎn)的路徑
     *
     * @param root   根結(jié)點(diǎn)
     * @param target 目標(biāo)結(jié)點(diǎn)
     * @param path   從根結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的路徑
     */
    public static void getNodePath(TreeNode root, TreeNode target, List<TreeNode> path) {
        if (root == null) {
            return;
        }
        // 添加當(dāng)前結(jié)點(diǎn)
        path.add(root);
        List<TreeNode> children = root.children;
        // 處理子結(jié)點(diǎn)
        for (TreeNode node : children) {
            if (node == target) {
                path.add(node);
                return;
            } else {
                getNodePath(node, target, path);
            }
        }
        // 現(xiàn)場(chǎng)還原
        path.remove(path.size() - 1);
    }
    /**
     * 找兩個(gè)路徑中的最后一個(gè)共同的結(jié)點(diǎn)
     *
     * @param p1 路徑1
     * @param p2 路徑2
     * @return 共同的結(jié)點(diǎn)，沒有返回null
     */
    public static TreeNode getLastCommonNode(List<TreeNode> p1, List<TreeNode> p2) {
        Iterator<TreeNode> ite1 = p1.iterator();
        Iterator<TreeNode> ite2 = p2.iterator();
        TreeNode last = null;
        while (ite1.hasNext() && ite2.hasNext()) {
            TreeNode tmp = ite1.next();
            if (tmp == ite2.next()) {
                last = tmp;
            }
        }
        return last;
    }
    /**
     * 找樹中兩個(gè)結(jié)點(diǎn)的最低公共祖先
     * @param root 樹的根結(jié)點(diǎn)
     * @param p1 結(jié)點(diǎn)1
     * @param p2 結(jié)點(diǎn)2
     * @return 公共結(jié)點(diǎn)，沒有返回null
     */
    public static TreeNode getLastCommonParent(TreeNode root, TreeNode p1, TreeNode p2) {
        if (root == null || p1 == null || p2 == null) {
            return null;
        }
        List<TreeNode> path1 = new LinkedList<>();
        getNodePath(root, p1, path1);
        List<TreeNode> path2 = new LinkedList<>();
        getNodePath(root, p2, path2);
        return getLastCommonNode(path1, path2);
    }
    public static void main(String[] args) {
        test01();
        System.out.println("==========");
        test02();
        System.out.println("==========");
        test03();
    }
    // 形狀普通的樹
    //             1
    //           /   \
    //         2      3
    //        /         \
    //      4            5
    //     / \        /  |  \
    //    6   7      8   9  10
    public static void test01() {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);
        TreeNode n6 = new TreeNode(6);
        TreeNode n7 = new TreeNode(7);
        TreeNode n8 = new TreeNode(8);
        TreeNode n9 = new TreeNode(9);
        TreeNode n10 = new TreeNode(10);
        n1.children.add(n2);
        n1.children.add(n3);
        n2.children.add(n4);
        n4.children.add(n6);
        n4.children.add(n7);
        n3.children.add(n5);
        n5.children.add(n8);
        n5.children.add(n9);
        n5.children.add(n10);
        System.out.println(getLastCommonParent(n1, n6, n8));
    }
    // 樹退化成一個(gè)鏈表
    //               1
    //              /
    //             2
    //            /
    //           3
    //          /
    //         4
    //        /
    //       5
    private static void test02() {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);
        n1.children.add(n2);
        n2.children.add(n3);
        n3.children.add(n4);
        n4.children.add(n5);
        System.out.println(getLastCommonParent(n1, n4, n5));
    }
    // 樹退化成一個(gè)鏈表，一個(gè)結(jié)點(diǎn)不在樹中
    //               1
    //              /
    //             2
    //            /
    //           3
    //          /
    //         4
    //        /
    //       5
    private static void test03() {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);
        TreeNode n6 = new TreeNode(6);
        n1.children.add(n2);
        n2.children.add(n3);
        n3.children.add(n4);
        n4.children.add(n5);
        System.out.println(getLastCommonParent(n1, n5, n6));
    }
}

運(yùn)行結(jié)果

http://wiki.jikexueyuan.com/project/for-offer/images/68.png" alt="" />