leetcode 95. Unique Binary Search Trees II 递归构造所有可能的搜索二叉树BST + 卡特兰数

布满荆棘的人生 2022-06-08 02:52 49阅读 0赞

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example,  
Given n = 3, your program should return all 5 unique BST’s shown below.

1 3 3 2 1  
\\ / / / \\ \\  
3 2 1 1 3 2  
/ / \\ \\  
2 1 2 3

这道题就是穷举所有可能的搜索二叉树BST的数量。就是求解卡特兰数。也可以参考这个题[ leetcode 96. Unique Binary Search Trees 卡特兰数][leetcode 96. Unique Binary Search Trees]

说实话，这种递归我写不出来，我是参考网上的教程做得，但是看到代码就自动应该是这么做得。

建议和[leetcode 87. Scramble String 字符串拼凑 && DFS深度优先搜索][leetcode 87. Scramble String _ _ DFS] 一起学习，因为我感觉递归思路相似

这道题的做法感觉和[leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal 中前序构造BST][leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal _BST] 和 [leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal 中后序构造BST][leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal _BST] 一起学习，因为做法类似

这道题可以和[leetcode 108. Convert Sorted Array to Binary Search Tree 构建平衡二叉搜索树 + DFS][leetcode 108. Convert Sorted Array to Binary Search Tree _ _ DFS] 一起学习

同时和这一道题[leetcode 241. Different Ways to Add Parentheses 深度优先遍历DFS + 类似构造所有的二叉搜索树][leetcode 241. Different Ways to Add Parentheses _DFS _] 很像，值得一起学习

还有这一道题[leetcode 282. Expression Add Operators 任意添加运算符计算结果 +深度优先遍历DFS][leetcode 282. Expression Add Operators _ _DFS]

这道题很值得学习。

代码如下：

import java.util.ArrayList;
    
    /*class TreeNode
    {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode(int x) { val = x; }
    }*/
    
    public class Solution
    {
        /*
         * http://blog.csdn.net/linhuanmars/article/details/24761437
         * 
         * 这道题是求解所有可行的二叉查找树，从Unique Binary Search Trees中我们已经知道，
         * 可行的二叉查找树的数量是相应的卡特兰数，不是一个多项式时间的数量级，所以我们要求
         * 解所有的树，自然是不能多项式时间内完成的了。算法上还是用求解NP问题的方法来求解，
         * 也就是N-Queens中介绍的在循环中调用递归函数求解子问题。思路是每次一次选取一个结点为根，
         * 然后递归求解左右子树的所有结果，最后根据左右子树的返回的所有子树，依次选取然后接上
         * （每个左边的子树跟所有右边的子树匹配，而每个右边的子树也要跟所有的左边子树匹配，总共
         * 有左右子树数量的乘积种情况），构造好之后作为当前树的结果返回。代码如下
         * */
        public ArrayList<TreeNode> generateTrees(int n) 
        {
            if(n<=0)
                return new ArrayList<TreeNode>();
            else
                return byRecursion(1,n);
        }
    
        private ArrayList<TreeNode> byRecursion(int left, int right) 
        {
            ArrayList<TreeNode> res=new ArrayList<>();
            if(left>right)
                res.add(null);
            else 
            {
                for(int i=left;i<=right;i++)
                {
                    ArrayList<TreeNode> leftChild=byRecursion(left, i-1);
                    ArrayList<TreeNode> rightChild=byRecursion(i+1, right);
                    for(int j=0;j<leftChild.size();j++)
                    {
                        for(int k=0;k<rightChild.size();k++)
                        {
                            TreeNode root=new TreeNode(i);
                            root.left=leftChild.get(j);
                            root.right=rightChild.get(k);
                            res.add(root);
                        }
                    }
                }
            }
            return res;
        }
    
    }

下面是C++的做法，这道题很棒，就是构造所有可能的二叉搜索树的情况，说实话我不会做，但是看到了网上的一个做法，感觉也很棒，需要记住好好学习

代码如下：

#include<iostream>
    #include <vector>
    
    using namespace std;
    
    
    /*
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    */
    
    
    class Solution 
    {
    public:
        vector<TreeNode*> generateTrees(int n) 
        {
            vector<TreeNode*> res;
            if (n <= 0)
                return res;
            res = byDFS(1,n);
            return res;
        }
    
        vector<TreeNode*> byDFS(int left, int right)
        {
            vector<TreeNode*> res;
            if (left > right)
                res.push_back(NULL);
            else
            {
                for (int i = left; i <= right; i++)
                {
                    vector<TreeNode*> leftChild = byDFS(left, i - 1);
                    vector<TreeNode*> rightChild = byDFS(i+1, right);
                    for (int j = 0; j < leftChild.size(); j++)
                    {
                        for (int k = 0; k < rightChild.size(); k++)
                        {
                            TreeNode* root = new TreeNode(i);
                            root->left = leftChild[j];
                            root->right = rightChild[k];
                            res.push_back(root);
                        }
                    }
                }
            }
            return res;
        }
    };

[leetcode 96. Unique Binary Search Trees]: http://blog.csdn.net/jackzhang_123/article/details/77948169
[leetcode 87. Scramble String _ _ DFS]: http://blog.csdn.net/jackzhang_123/article/details/77942734
[leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal _BST]: http://blog.csdn.net/jackzhang_123/article/details/77977697
[leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal _BST]: http://blog.csdn.net/jackzhang_123/article/details/77977904
[leetcode 108. Convert Sorted Array to Binary Search Tree _ _ DFS]: http://blog.csdn.net/jackzhang_123/article/details/77978036
[leetcode 241. Different Ways to Add Parentheses _DFS _]: http://blog.csdn.net/jackzhang_123/article/details/78092468
[leetcode 282. Expression Add Operators _ _DFS]: http://blog.csdn.net/jackzhang_123/article/details/78119663