统计和生成所有不同的二叉树

题目：不同的二叉搜索树 & 不同的二叉搜索树 II

《程序员代码面试指南》第53题 P173 难度：尉★★☆☆

原问题只是统计二叉树的数量。

首先，如果中序遍历有序且无重复值，则二叉树必为搜索二叉树。

假设num(a)代表a个节点的搜索二叉树有多少种可能。再假设序列为{1,…,i,…,N}。

如果以i作为头节点，则左边和右边分别作为其左右子树。显然，这种情况下有num(i-1)×num(N-i)种可能。

另外，当i=1或者i=N时，有num(0)×num(N-1)=num(N-i)种可能。

书上也提到，利用了动态规划来加速计算的过程。代码如下：

public int numTrees(int n) {
    if (n < 2) {
        return 1;
    }
    int[] num = new int[n + 1];
    num[0] = 1;
    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < i + 1; j++) {
            num[i] += num[j - 1] * num[i - j];
        }
    }
    return num[n];
}

进阶问题则是要生成所有不同的二叉树。

思路和原问题类似。枚举每一个值作为头节点，并且通过{1...i-1}和{i+1...N}递归生成左右子树。

public List<Node> generateTrees(int n) {
    return generate(1, n);
}

public List<Node> generate(int start, int end) {
    List<Node> res = new LinkedList<Node>();
    if (start > end) {
        res.add(null);
    }
    Node head = null;
    for (int i = start; i < end + 1; i++) {
        head = new Node(i);
        List<Node> lSubs = generate(start, i - 1);
        List<Node> rSubs = generate(i + 1, end);
        for (Node l : lSubs) {
            for (Node r : rSubs) {
                head.left = l;
                head.right = r;
                res.add(cloneTree(head));
            }
        }
    }
    return res;
}

public Node cloneTree(Node head) {
    if (head == null) {
        return null;
    }
    Node res = new Node(head.value);
    res.left = cloneTree(head.left);
    res.right = cloneTree(head.right);
    return res;
}

需要额外注意一下，这个克隆节点的意义。如果不新生成节点，把前一个头节点放入list，再修改其左右子树，以为此时是一个新的头节点了，把它放入了list，但是此时之前放入list中的头节点的值也发生了变化。因为它们的引用相同，指向同一个区域了。导致在list中相同的头节点的结构全部一样了。这肯定是不行的。所以对于每一种可能性都要新生成一个头节点。