/**
 * 输入一棵二叉查找树的两个结点，返回它们的最低公共祖先。
 */
public class LastSameInBST {
    private class Node {
        private Node left, right;
        private int val;

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

    /**
     * 二查平衡树中
     * @param root
     * @param a
     * @param b
     * @return
     */
    public Node findLastSameInBST(Node root, Node a, Node b) {
        Node cur = root;
        while (cur != null){
            if (a.val < cur.val && b.val < cur.val){
                cur = cur.left;
            }else if (a.val > cur.val && b.val > cur.val){
                cur = cur.right;
            }else {
                return cur;
            }

        }
        return null;
    }


}

/**
 * 输入一棵普通树（拥有指向父结点的指针）的两个结点，返回它们的最低公共祖先。。
 */
public class LastSameInParent {

    private class Node {
        Node parent;
        int val;

        public Node() {
            this.val = val;
        }
    }
    /**
     * 存在指向父节点的指针
     * 求出长度以后，让其中一个先移动多出来的长度，然后一起移动找到交点
     * @param a
     * @param b
     * @return
     */
    public Node findLastSameInParent(Node a, Node b) {

        int len1 = 0;
        int len2 = 0;
        Node cur1 = a;
        while (cur1 != null){
            len1++;
            cur1 = cur1.parent;
        }
        Node cur2 = b;
        while (cur2 != null){
            len2++;
            cur2 = cur2.parent;
        }
        if (len1 > len2){
            for (int i=0;i<(len1 - len2);i++){
                a = a.parent;
            }
        }
        if (len1 < len2){
            for (int i=0;i<(len2 - len1);i++){
                b = b.parent;
            }
        }
        while (a != null && b != null){
            if (a == b) return a;
            a = a.parent;
            b = b.parent;
        }
        return null;

    }
}

/**
 * 输入一棵普通树的两个结点，返回它们的最低公共祖先。
 */
public class LastSameInTree {
    private class Node {
        List<Node> children;
        int val;
    }

    /**
     * 递归形成两个链表，从根节点开始找相同的节点
     * @param root
     * @param a
     * @param b
     * @return
     */
    public Node findLastSame(Node root, Node a, Node b) {
        if (root == null || a == null || b == null) return root;
        LinkedList<Node> path1 = new LinkedList<>();
        LinkedList<Node> path2 = new LinkedList<>();
        //分别以a，b为终点
        collectNode(root, a, path1);
        collectNode(root, b, path2);
        return getLastSameNode(path1, path2);
     }

    private Node getLastSameNode(LinkedList<Node> path1, LinkedList<Node> path2) {
        while (!path1.isEmpty() && !path2.isEmpty()){
            if (path1.peekFirst() == path2.pollFirst()){
                return path1.pollFirst();
            }
        }
        return null;
    }

    private boolean collectNode(Node root, Node node, LinkedList<Node> path) {
        if (root == node) return true;
        path.add(root);
        for (Node child : root.children){
            if (collectNode(child, node, path)) return true;
        }
        //如果没有找到目标节点，则先移除，尝试别的路径
        path.removeLast();
        return false;
    }
}