二叉树--查找给定两个节点最下公共祖先

最近真是多事之秋，好好的日更被断了，计划永远是赶不上变化的，乘着睡前补上吧。
查找给定两个节点最下公共祖先，俗称LCA算法。

题目介绍

给定任意一个二叉树，以及两个节点，查找它们最小公共祖先。题目比较容易理解，就不补图了。

实现思路

先用暴力算法来实现吧，具体流程如下：
1、先定义两个节点List，分别用来存放给定两个节点的路径上所有节点。
2、分别递归遍历两次树，将路径填充到上述定义的List中。
3、最后将根节点加入到List尾部，因为路径必定包含根节点，所以最大的公共祖先就是根节点。
4、此时两个List的顺序为路径节点的倒叙，因此我们只要使用两个for循环找到第一个相等的节点就是所要求的解。

实现代码

public class SolutionLCA {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> lPath = new ArrayList<>();
        List<TreeNode> rPath = new ArrayList<>();

        fill(root, p, lPath);
        fill(root, q, rPath);

        lPath.add(root);
        rPath.add(root);

        for (TreeNode lTreeNode : lPath) {
            for (TreeNode rTreeNode : rPath) {
                if (lTreeNode.val == rTreeNode.val) {
                    return lTreeNode;
                }
            }
        }
        return root;
    }

    public boolean fill(TreeNode root, TreeNode s, List<TreeNode> path) {

        if (null == root) {
            return false;
        }

        if (root.val == s.val) {
            return true;
        }

        boolean lExists = fill(root.left, s, path);
        if (lExists) {
            path.add(root.left);
            return true;
        }

        boolean rExists = fill(root.right, s, path);
        if (rExists) {
            path.add(root.right);
            return true;
        }

        return false;
    }
}

算法相关实现源码地址：https://github.com/xiekq/rubs-algorithms