最近公共祖先问题

写个题解记录下。

思路：

1. 搜索两节点，并记录由搜索节点至根节点的节点路由表；
2. 顺序遍历一路由表，首先出现在另一表中的节点即为最近公共祖先；

    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {

        List<TreeNode> l1 = new ArrayList<>(), l2 = new ArrayList<>();

        boolean r1 = routed(l1, root, o1), r2 = routed(l2, root, o2);

        //  root不可达
        if (root == null || !r1 || !r2) {
            throw new RuntimeException("root is invalid or not reachable!");
        }

        for (TreeNode t : l1) {
            if(l2.contains(t)) return t.val;
        }

        return root.val;
    }

    private boolean routed(List<TreeNode> nodes, TreeNode t, int val){

        if(t == null) return false;

        // 判定当前节点是否位于根节点至搜索节点的路由链路上
        boolean anc = t.val == val || routed(nodes, t.left, val) || routed(nodes, t.right, val);

        // 是路由链路上的节点，则添加。
        // 注意顺序：先判定左右子节点，再添加元素。否则路由列表方向由根节点指向待查找节点。
        if(anc) nodes.add(t);

        return anc;
    }