标签搜索

目 录CONTENT

文章目录

不同的二叉搜索树.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 7 阅读 / 1,448 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

不同的二叉搜索树

@[toc]

一、问题描述

在这里插入图片描述

二、分析

  •  在已知前n-1个数的二叉搜索树数目后,插入第n个数,有哪些情况?
  •  1.第n个数做根节点,前n-1个数形成其左子树,右子树为0个数,dp[n-1]*dp[0]种
  •  2.第n-1个数做根节点,左子树为前n-2个数,右子树为第n个数,dp[n-2]*dp[1]种
  •  ...
  •  n-i+1.第i个数做根节点,左子树为前i-1个数,右子树为后n-i个数,dp[i-1]*dp[n-i]种
  •  ...n.第1个数做根节点,左子树为0个数,右子树为后n-1个数,dp[0]*dp[n-1]种
  •  我们将所有情况的二叉搜索树加起来即可

三、代码

class Solution {
public:
    int numTrees(int n) {
        // 二叉搜索数的特征,左子树小于根,右子树大于根
        vector<int> dp(n + 1, 0);
        // dp[0]初始化为1
        dp[0] = 1;  
        // 从1...n的二叉搜索数数目
        for(int i = 1; i <= n; i++)  
        	// 逐步选用1...n作为根节点
            for(int j = 1; j <= i; j++)  
            	// 左侧j-1个数,右侧i-j个数
                dp[i] += dp[j - 1] * dp[i - j]; 
                 
        return dp[n]; 
    }
};

四、问题描述

在这里插入图片描述

五、分析

方法:递归

  •  首先来计数需要构建的二叉树数量。可能的二叉搜素数数量是一个 卡特兰数。
  •  我们跟随上文的逻辑,只是这次是构建具体的树,而不是计数。
  •  我们从序列 1 ..n 中取出数字 i,作为当前树的树根。于是,剩余 i - 1 个元素可用于左子树,n - i 个元素用于右子树。
  •  如 前文所述,这样会产生 G(i - 1) 种左子树 和 G(n - i) 种右子树,其中 G 是卡特兰数。
    在这里插入图片描述
  •  现在,我们对序列 1 ... i - 1 重复上述过程,以构建所有的左子树;然后对 i + 1 ... n 重复,以构建所有的右子树
  •  这样,我们就有了树根 i 和可能的左子树、右子树的列表
  •  最后一步,对两个列表循环,将左子树和右子树连接在根上

六、代码

class Solution {
public:
    vector<TreeNode*> helper(int start,int end)
    {
        vector<TreeNode*> ret;
        if(start > end)
            ret.push_back(nullptr);
        
        // pick up a root
        for(int i = start;i <= end;i++)
        {
        	// 如果i被选为根,所有可能的左子树
            vector<TreeNode*> left = helper(start,i - 1);
            // 如果i被选为根,所有可能的右子树
            vector<TreeNode*> right = helper(i + 1,end);
            // 将左右树连接到根i
            for(auto l : left)
            {
                for(auto r : right)
                {
                    TreeNode* root = new TreeNode(i);
                    root -> left = l;
                    root -> right = r;
                    ret.push_back(root);
                }
            }
        }
        return ret;
    }
    
    vector<TreeNode*> generateTrees(int n) 
    {
        vector<TreeNode*> ret;
        if(n == 0)
            return ret;    
        ret = helper(1,n);
        return ret;
    }
};
0

评论区