不同的二叉搜索树

问题陈述

思路分析

构建一棵二叉搜索树

构建一颗二叉搜索树很简单，只需要选择一个根结点，然后递归去构建其左右子树。

1
2
3
4
5
6
7
8
9
10
11
public TreeNode creatBinaryTree(int n){
    return helper(1,n);
}
private TreeNode helper(int start,int end){
    if(start>end) return null;
    int val=(start+end)/2;
    TreeNode root=new TreeNode(val);
    root.left=helper(start,val-1);
    root.right=helper(val+1,end);
    return root;
}

要构建多颗二叉树，问题就在于如何选择不同的根节点，以构建不同的树和子树。

在上面的代码中，在选择根结点的时候，可以这样改造

1
2
3
4
5
// 选择所有可能的根结点
for(int i = start; i <= end; i++){
    TreeNode root = new TreeNode(i);
    ...
}

但是如果按照上述递归函数的方法写，每次递归只能返回一颗树，我们需要的是多颗树，我们可以将不同的根结点装入List然后返回，实际上，上述代码可以改写成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public List<TreeNode> helper(int start, int end){
    List<TreeNode> list = new ArrayList<>();        

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

    for(int i = start; i <= end; i++){
        TreeNode root = new TreeNode(i);
        ...
        ...
        // 装入所有根结点
        list.add(root);
    }

    return list;
}

很显然，现在问题变成了如何构建root的左右子树，我们抛开复杂的递归函数，只关心递归的返回值，每次选择根结点root，我们

  • 递归构建左子树，并拿到左子树所有可能的根结点列表left

  • 递归构建右子树，并拿到右子树所有可能的根结点列表right

    这个时候我们有了左右子树列表，我们的左右子树都是各不相同的，因为根结点不同，我们如何通过左右子树列表构建出所有的以root为根的树呢？

我们固定一个左孩子，遍历右子树列表，那么以当前为root根结点的树个数就为left.size() * right.size()个。

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
26
27
28
29
30
31
32
33
class Solution {
    public List<TreeNode> generateTrees(int n) {
        if(n < 1)
            return new ArrayList<>();
        return helper(1, n);
    }
   public List<TreeNode> helper(int start, int end){
    List<TreeNode> list = new ArrayList<>();

    if(start > end){
        // 如果当前子树为空，不加null行吗？
        list.add(null);
        return list;
    }

    for(int i = start; i <= end; i++){
        // 想想为什么这行不能放在这里，而放在下面？
        // TreeNode root = new TreeNode(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;
                list.add(root);
            }
        }
    }
    return list;
}

}
关于TreeNode root = new TreeNode(i)的放置的位置问题
如果这行代码放置在注释的地方，会造成一个问题，就是以当前为root根结点的树个数就
num = left.size() * right.size() > 1时，num棵子树会共用这个root结点，在下面两层for循环中，root的左右子树一直在更新，如果每次不新建一个root，就会导致num个root为根节点的树都相同。

关于如果当前子树为空，不加null行不行的问题
显然，如果一颗树的左子树为空，右子树不为空，要正确构建所有树，依赖于对左右子树列表的遍历，也就是上述代码两层for循环的地方，如果其中一个列表为空，那么循环都将无法进行。

作者：antione
链接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/cong-gou-jian-dan-ke-shu-dao-gou-jian-suo-you-shu-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。