二刷Leetcode-Days02

栈和队列：

   /**
     * 232. 用栈实现队列
     * 队列的先进先出可以使用两个栈stackIn和stackOut来实现；
     * 出队列前，如果 stackOut 不为空，表示队列当前值在上一轮已进入 stackOut 中，还没有被消费掉
     * 若 stackOut 为空，也就是队列当前值还在 stackIn 中，为了确保先进先出，就将 stackIn 中全部 push 到 stackOut 里
     */
    class MyQueue {
        Stack<Integer> stackIn;
        Stack<Integer> stackOut;

        public MyQueue() {
            stackIn = new Stack<>();
            stackOut = new Stack<>();
        }

        public void push(int x) {
            stackIn.push(x);
        }

        public int pop() {
            dumpStackIn();
            return stackOut.pop();
        }

        public int peek() {
            dumpStackIn();
            return stackOut.peek();
        }

        public boolean empty() {
            return stackIn.isEmpty() && stackOut.isEmpty();
        }

        private void dumpStackIn() {
            if (!stackOut.isEmpty()) {
                return;
            }
            while (!stackIn.isEmpty()) {
                stackOut.push(stackIn.pop());
            }
        }
    }

二叉树：

   /**\
     * 深度遍历（前中后序，所谓前中后序，就是中间结点的位置决定的）
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<Integer> res = new ArrayList<>();
        preorder(root, res);
        return res;
    }

    public void preorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        preorder(root.left, res);
        preorder(root.right, res);
    }

    public void inorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        preorder(root.left, res);
        res.add(root.val);
        preorder(root.right, res);
    }

    public void postorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        preorder(root.left, res);
        res.add(root.val);
        preorder(root.right, res);
    }

回溯：

    /**
     * 77. 组合
     * @param n
     * @param k
     * @return 返回范围 [1, n] 中所有可能的 k 个数的组合。
     */
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> restlt = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        combine_backtracking(n, k, 1, restlt, path);
        return restlt;
    }

    /**
     * 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex
     * @param startIndex 用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,...,n] ）。
     */
    public void combine_backtracking(int n, int k, int startIndex, List<List<Integer>> restlt, LinkedList<Integer> path) {
        // 终止条件（层数够了，就是二叉树中的遍历到叶子结点了）
        // n相当于树的宽度，k相当于树的深度。
        if (k == path.size()) {
            restlt.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
            path.add(i);
            combine_backtracking(n, k, i + 1, restlt, path);
            path.removeLast();
        }
    }