算法训练——递归

递归

1.树的遍历

1497. 树的遍历 - AcWing题库

一个二叉树，树中每个节点的权值互不相同。

现在给出它的后序遍历和中序遍历，请你输出它的层序遍历。

输入格式

第一行包含整数 N，表示二叉树的节点数。

第二行包含 N个整数，表示二叉树的后序遍历。

第三行包含 N 个整数，表示二叉树的中序遍历。

输出格式

输出一行 N 个整数，表示二叉树的层序遍历。

数据范围

1≤N≤30
官方并未给出各节点权值的取值范围，为方便起见，在本网站范围取为 1∼N

输入样例：

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

输出样例：

4 1 6 3 5 7 2

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;

/**
 * 1497. 树的遍历
 * https://www.acwing.com/problem/content/1499/
 *
 * @author yangxiaozhuo
 * @date 2023/02/20
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        int[] follow = new int[n];
        int[] middle = new int[n];
        String[] s = in.readLine().split(" ");
        for (int i = 0; i < follow.length; i++) {
            follow[i] = Integer.parseInt(s[i]);
        }
        s = in.readLine().split(" ");
        for (int i = 0; i < middle.length; i++) {
            middle[i] = Integer.parseInt(s[i]);
        }
        int[] res = new int[n];
        int index = 0;
        Node root = fun(middle, 0, middle.length - 1, follow, 0, follow.length - 1);
        ArrayDeque<Node> nodes = new ArrayDeque<>();
        nodes.add(root);
        while (index < n) {
            int size = nodes.size();
            for (int i = 0; i < size; i++) {
                Node node = nodes.removeFirst();
                res[index++] = node.val;
                if (node.left != null) {
                    nodes.addLast(node.left);
                }
                if (node.right != null) {
                    nodes.addLast(node.right);
                }
            }
        }
        StringBuilder sber = new StringBuilder();
        for (int num : res) {
            sber.append(num);
            sber.append(" ");
        }
        System.out.println(sber.toString());
    }

    private static Node fun(int[] middle, int a, int b, int[] follow, int x, int y) {
        if (x > y) {
            return null;
        }
        Node node = new Node(follow[y]);
        for (int i = a; i <= b; i++) {
            if (middle[i] == follow[y]) {
                //
                node.left = fun(middle, a, i - 1, follow, x, x + i - a - 1);
                node.right = fun(middle, i + 1, b, follow, y - b + i, y - 1);
            }
        }
        return node;
    }

    static class Node {
        int val;
        Node left;
        Node right;

        public Node() {
        }

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

2.递归实现指数型枚举

92. 递归实现指数型枚举 - AcWing题库

从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式

输入一个整数 n。

输出格式

每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好 11 个空格隔开。

对于没有选任何数的方案，输出空行。

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围

1≤n≤15

输入样例：

3

输出样例：

3
2
2 3
1
1 3
1 2
1 2 3

代码

import java.io.*;
/**
 * 92. 递归实现指数型枚举
 * https://www.acwing.com/problem/content/94/
 *
 * @author yangxiaozhuo
 * @date 2023/02/20
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        int[] ints = new int[n];
        dfs(ints, 1);
        ints[0] = 1;
        dfs(ints, 1);
    }

    public static void dfs(int[] ints, int at) {
        if (at == ints.length) {
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < ints.length; i++) {
                if (ints[i] == 1) {
                    sb.append(i + 1);
                    sb.append(" ");
                }
            }
            if (sb.length() > 1) {
                sb.deleteCharAt(sb.length() - 1);
            }
            System.out.println(sb.toString());
            return;
        }
        dfs(ints, at + 1);
        ints[at] = 1;
        dfs(ints, at + 1);
        ints[at] = 0;
    }
}

3.树的遍历

94. 递归实现排列型枚举 - AcWing题库

把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。

输入格式

一个整数 n。

输出格式

按照从小到大的顺序输出所有方案，每行 11 个。

首先，同一行相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

数据范围

1≤n≤9

输入样例：

3

输出样例：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

/**
 * 94. 递归实现排列型枚举
 * https://www.acwing.com/problem/content/96/
 *
 * @author yangxiaozhuo
 * @date 2023/02/20
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        int[] vis = new int[n];
        ArrayList<Integer> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            vis[i] = 1;
            list.add(i + 1);
            dfs(list, vis);
            list.remove(list.size() - 1);
            vis[i] = 0;
        }
    }

    public static void dfs(ArrayList<Integer> list, int[] vis) {
        if (list.size() == vis.length) {
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < list.size(); i++) {
                sb.append(list.get(i));
                sb.append(" ");

            }
            sb.deleteCharAt(sb.length() - 1);
            System.out.println(sb.toString());
            return;
        }
        for (int i = 0; i < vis.length; i++) {
            if (vis[i] == 0) {
                vis[i] = 1;
                list.add(i + 1);
                dfs(list, vis);
                vis[i] = 0;
                list.remove(list.size() - 1);
            }
        }
    }
}

4.递归实现组合型枚举

93. 递归实现组合型枚举 - AcWing题库

从 1∼n 这 n个整数中随机选出 m 个，输出所有可能的选择方案。

输入格式

两个整数 n,m ,在同一行用空格隔开。

输出格式

按照从小到大的顺序输出所有方案，每行 11 个。

首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。

数据范围

n>0
0≤m≤n
n+(n−m)≤25

输入样例：

5 3

输出样例：

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

/**
 * 93. 递归实现组合型枚举
 * https://www.acwing.com/problem/content/95/
 *
 * @author yangxiaozhuo
 * @date 2023/02/20
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] s = in.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        int[] vis = new int[n + 1];
        ArrayList<Integer> list = new ArrayList<>(m);
        for (int i = 1; i <= n; i++) {
            vis[i] = 1;
            list.add(i);
            dfs(list, vis, m, i);
            vis[i] = 0;
            list.remove(list.size() - 1);
        }
    }

    public static void dfs(ArrayList<Integer> list, int[] vis, int m, int at) {
        if (list.size() == m) {
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < list.size(); i++) {
                sb.append(list.get(i));
                sb.append(" ");

            }
            sb.deleteCharAt(sb.length() - 1);
            System.out.println(sb.toString());
            return;
        }
        for (int i = at + 1; i < vis.length; i++) {
            if (vis[i] == 0) {
                vis[i] = 1;
                list.add(i);
                dfs(list, vis, m, i);
                vis[i] = 0;
                list.remove(list.size() - 1);
            }
        }
    }
}