96. 不同的二叉搜索树 II Krains 2020-09-03 树

Krains

发布于 2020-09-10 18:37:45

2870

发布于 2020-09-10 18:37:45

文章被收录于专栏：KrainsKrains

题目链接

构建一颗二叉搜索树

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

public TreeNode createBinaryTree(int n){
    return helper(1, n);
}

public TreeNode helper(int start, int end){
    if(start > end)
        return null;

    // 这里可以选择从start到end的任何一个值做为根结点，
    // 这里选择它们的中点，实际上，这样构建出来的是一颗平衡二叉搜索树
    int val = (start + end) / 2;
    TreeNode root = new TreeNode(val);

    root.left = helper(start, val - 1);
    root.right = helper(val + 1, end);

    return root;
}

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

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

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

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

    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()个。

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循环的地方，如果其中一个列表为空，那么循环都将无法进行。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-09-03，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度