【剑指Offer】树中两个结点的最低公共祖先

题目

输入两个树结点，求它们的最低公共祖先。这棵树是普通的树，而且树中的结点没有指向父结点的指针。

实现

public class TreeNode {
    int val = 0;
    List<TreeNode> children = new ArrayList<>();

    public TreeNode(int val) {
        this.val = val;
    }
}

public TreeNode getLastCommonParent(TreeNode root, TreeNode node1, TreeNode node2) {
    if (root == null || node1 == null || node2 == null)
        return null;

    List<TreeNode> path1 = new ArrayList<>();
    getPath(path1, root, node1);
    List<TreeNode> path2 = new ArrayList<>();
    getPath(path2, root, node2);

    Iterator<TreeNode> iterator1 = path1.iterator();
    Iterator<TreeNode> iterator2 = path2.iterator();
    TreeNode parent = null;

    while (iterator1.hasNext() && iterator2.hasNext()) {
        TreeNode n1 = iterator1.next();
        TreeNode n2 = iterator2.next();

        if(n1 != n2)
            break;

        parent = n1;
    }

    return parent;
}

private void getPath(List<TreeNode> path, TreeNode root, TreeNode node) {
    if (root == null)
        return;

    path.add(root);

    if (root == node)
        return;

    for (TreeNode child : root.children) {
        getPath(path, child, node);

        if (path.contains(node))
            break;
    }

    if (!path.contains(node))
        path.remove(path.size() - 1);
}