按词法顺序生成N个节点的所有二叉树

Answer 1

我不会给你直接的解决办法。但我将在这里给出一个类似问题的解决方案：给定n，生成所有结构上唯一的BST（二分搜索树），存储值1.…n。

我想你稍微修改一下我的解决方案来解决你的问题并不难。

public class Solution {
    public List<TreeNode> generateTrees(int n) {
        return helper(1, n);
    }

    private List<TreeNode> helper(int start, int end) {
        List<TreeNode> result = new ArrayList<TreeNode>();

        if (start > end) {
            result.add(null);
            return result;
        }

        // You just need to understand how below for loop works.
        for (int i = start; i <= end; i++) {
            List<TreeNode> left = helper(start, i - 1);
            List<TreeNode> right = helper(i + 1, end);
            for (TreeNode l : left) {
                for (TreeNode r : right) {
                    TreeNode root = new TreeNode(i);
                    root.left = l;
                    root.right = r;
                    result.add(root);
                }
            }
        }

        return result;
    }
}

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; left = null; right = null; }
}

使用动态编程，解决方案非常简单。