[leetcode] 95. Unique Binary Search Trees II

[leetcode] 95. Unique Binary Search Trees II

Description

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

Example:

Input:

3

Output:

[ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3]]

Explanation:

The above output corresponds to the 5 unique BST's shown below: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3

分析

题目的意思是：给定一个数n，生成所有类型的二叉查找数，节点的值为1~n.

记得旷世科技的面试官问过我这道题，题目本身是一个递归的题目，思路是把每个节点都当成一个根节点，然后左右递归建树就行了，终止条件为遍历到第n个值了。

代码

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector generateTrees(int n) { vector result; if(n<1){ return result; } result=solve(1,n); return result; } vector solve(int start,int n){ vector subTree; if(start>n){ subTree.push_back(NULL); return subTree; } for(int i=start;i<=n;i++){ vector leftSubs=solve(start,i-1); vector rightSubs=solve(i+1,n); for(auto left:leftSubs){ for(auto right:rightSubs){ TreeNode* node=new TreeNode(i); node->left=left; node->right=right; subTree.push_back(node); } } } return subTree; }};

参考文献

​​[编程题]unique-binary-search-trees-ii​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。