LeetCode:95

Posted on 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public List<TreeNode> generateTrees(int n) {
        if(n<=0) {return new ArrayList<>();}
        return helper(1,n);
    }
    
    public static List<TreeNode> helper(int start, int end) {
        List<TreeNode> res = new ArrayList<>();
        if(end<start) {res.add(null);}
        for(int i = start; i<=end; i++) {
            List<TreeNode> leftList = helper(start,i-1);
            List<TreeNode> rightList = helper(i+1,end);
            for(TreeNode leftNode:leftList) {
                for(TreeNode rightNode:rightList) {
                    // 为了避免重复的答案，在循环中新建一个root
                    TreeNode root = new TreeNode(i);
                    root.left = leftNode;
                    root.right = rightNode;
                    res.add(root);
                }
            }
        }
        return res; 
    }
}
  1. 确定根节点
  2. 小于根节点的值生成左子树，大于根节点的值生成右子树
  3. 左子树和右子树进行排列组合