// Runtime: 6 ms, faster than 68.68% of Java online submissions for Lowest Common Ancestor of a Binary Tree.
// Memory Usage: 35.8 MB, less than 5.55% of Java online submissions for Lowest Common Ancestor of a Binary Tree.
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        LinkedList<TreeNode> pPath = new LinkedList<>();
        search(root, p, pPath);

        TreeNode last, parent;

        last = pPath.pollLast();
        if (search2(last, q)) return last;

        for (;;) {
            if (last == q) return last;

            parent = pPath.pollLast();
            if (parent == q) return parent;
            if (parent == null) break;

            TreeNode alt = (parent.left == last) ? parent.right: parent.left;
            if (alt != null && search2(alt, q)) return parent;

            last = parent;
        }

        return null;
    }

    private boolean search(TreeNode root, TreeNode node, LinkedList<TreeNode> path) {
        path.add(root);
        if (root == node) {
            return true;
        }
        if (root.left != null && search(root.left, node, path)) {
            return true;
        }
        if (root.right != null && search(root.right, node, path)) {
            return true;
        }
        path.removeLast();
        return false;
    }

     private boolean search2(TreeNode root, TreeNode node) {
        if (root == node) {
            return true;
        }
        if (root.left != null && search2(root.left, node)) {
            return true;
        }
        if (root.right != null && search2(root.right, node)) {
            return true;
        }
        return false;
    }
}