java - 递归打印所有路径的树遍历的复杂性

问题描述

如果给出输入，我编写了一个程序来查找所有有效的参数组合N。应该有N多个参数。例如，如果N = 2，答案将是()(), (())，如果N = 3答案将是((())), (())(), ()(()), ()()(), (()())。

我已经在 Java 中使用二叉树实现了该解决方案。这是我的解决方案。

class Node {
    char value;
    Node right;
    Node left;

    public Node(char value) {
        this.value = value;
    }

    public void insertRight(char value) {
        Node node = new Node(value);
        this.right = node;
    }

    public void insertLeft(char value) {
        Node node = new Node(value);
        this.left = node;
    }
}

public class App
{
    private static final int N = 3;

    public static void main (String[] args)
    {
        Node tree = new Node('(');

        insertNodes(tree, N - 1, 1);

        printParams("", tree);
    }

    private static void insertNodes(Node currentNode, int remainingOpen, int remainingClose) {
        if (remainingOpen > 0) {
            currentNode.insertLeft('(');
            insertNodes(currentNode.left, remainingOpen - 1, remainingClose + 1);
        }
        if (remainingClose > 0) {
            currentNode.insertRight(')');
            insertNodes(currentNode.right, remainingOpen, remainingClose - 1);
        }
    }

    private static void printParams(String paramStr, Node node) {
        paramStr = paramStr + node.value;
        if (node.left == null && node.right == null) {
            System.out.println(paramStr);
            return;
        } 



        if (node.left != null) 
            printParams(paramStr, node.left);

        if (node.right != null)
            printParams(paramStr, node.right);
    }
}

我想知道这个解决方案的复杂性。创建树的复杂性是多少，遍历每条路径的复杂性是多少？

我知道，2 * N每条路径中都会有节点，并且最多会有2^2N孩子。如果我们从根开始遍历每条路径，复杂度可能是N * 2 ^ 2N. 但是，当涉及递归时，我无法考虑复杂性。

标签： javatime-complexitybinary-treetree-traversal

java - 递归打印所有路径的树遍历的复杂性

问题描述

解决方案

推荐阅读