[LeetCode]95.Unique Binary Search Trees II

简介:

【题目】

Given 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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.


【分析】

参考:[LeetCode]96.Unique Binary Search Trees

【代码】

/*********************************
*   日期:2014-12-27
*   作者:SJF0115
*   题目: 95.Unique Binary Search Trees II
*   来源:https://oj.leetcode.com/problems/unique-binary-search-trees-ii/
*   结果:AC
*   来源:LeetCode
*   总结:
**********************************/
#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) {
        if (n <= 0){
            return generate(1, 0);
        }//if
        else{
            return generate(1, n);
        }
    }//
private:
    // 返回根节点结合
    vector<TreeNode*> generate(int start,int end){
        vector<TreeNode*> subTree;
        if(start > end){
            subTree.push_back(NULL);
            return subTree;
        }//if
        // i作为根节点
        for(int i = start;i <= end;i++){
            // 以i为根节点的树,其左子树由[start,i-1]构成,其右子树由[i+1,end]构成。
            // 返回的是不同二叉查找树的根节点,几种二叉查找树就返回几个根节点
            vector<TreeNode*> leftSubTree = generate(start,i-1);
            vector<TreeNode*> rightSubTree = generate(i+1,end);
            // 左子树右子树跟根节点连接
            // 以i为根的树的个数,等于左子树的个数乘以右子树的个数
            for(int j = 0;j < leftSubTree.size();j++){
                for(int k = 0;k < rightSubTree.size();k++){
                    TreeNode* node = new TreeNode(i);
                    node->left = leftSubTree[j];
                    node->right = rightSubTree[k];
                    subTree.push_back(node);
                }//for
            }//for
        }//for
        return subTree;
    }//
};
// 先序遍历
void PreOrder(TreeNode* root){
    if(root == NULL){
        return;
    }//if
    cout<<root->val<<" ";
    PreOrder(root->left);
    PreOrder(root->right);
}

int main() {
    Solution solution;
    vector<TreeNode*> vec = solution.generateTrees(3);
    for(int i = 0;i < vec.size();i++){
        TreeNode* root = vec[i];
        PreOrder(root);
        cout<<endl;
    }
}







目录
相关文章
Leetcode Minimum Depth of Binary Tree (面试题推荐)
计算树的最小深度 很简单的一道题,只需要遍历一次树,到叶子节点的时候计算一下深度和当前最小深度比较,保存最小值就行。 我在这用了一个全局变量 mindepth。总感觉我这代码写的不够简练,求更精简的方法。
48 0
Leetcode Binary Tree Postorder Traversal(面试题推荐)
非递后续归遍历二叉树,肯定得用到栈。先序遍历很好写,但后续遍历就不是那么容易了。 只需要设置个指针pre,指向最后输出的那个节点就行了,只要判断cur指针指向的是上次输出节点的父节点,且cur无其他未遍历的节点,这个时候就把cur节点输出即可,然后更改pre。原理是要遍历当前节点,其所有子节点都必须遍历完,因为肯定是先左后右,所以只需一个指针保持前一次输出的结果即可。
54 0
Leetcode 236. Lowest Common Ancestor of a Binary Tree
根据LCA的定义,二叉树中最小公共祖先就是两个节点p和q最近的共同祖先节点,LCA的定义没什么好解释的,主要是这道题的解法。
41 0
LeetCode contest 190 5418. 二叉树中的伪回文路径 Pseudo-Palindromic Paths in a Binary Tree
LeetCode contest 190 5418. 二叉树中的伪回文路径 Pseudo-Palindromic Paths in a Binary Tree
|
算法 Python
LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree
LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree
LeetCode 102. 二叉树的层序遍历 Binary Tree Level Order Traversal
LeetCode 102. 二叉树的层序遍历 Binary Tree Level Order Traversal
LeetCode 104. 二叉树的最大深度 Maximum Depth of Binary Tree
LeetCode 104. 二叉树的最大深度 Maximum Depth of Binary Tree
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
60 6
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
121 2