【LeetCode】Unique Binary Search Trees I II

本文主要是介绍【LeetCode】Unique Binary Search Trees I II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、Unique Binary Search Trees 
Total Accepted: 11405 Total Submissions: 32197 My Submissions
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,

Given n = 3, there are a total of 5 unique BST's.

2、Unique Binary Search Trees II
Total Accepted: 6139 Total Submissions: 23434 My Submissions
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.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".
求解二叉搜索树所有的构成方式，其实是典型的递归。
每棵二叉树的构成，应该是以第i个点为根节点，以1到i-1为左子树，以i+1到n为右子树的所有组合。
1求解数目，2求解所有方式。

1 Java AC

public class Solution {public int numTrees(int n) {return addAllNum(1, n);}private int addAllNum(int start, int end){if(start >= end){return 1;}int allNum = 0;for(int i = start; i <= end; i++){allNum += addAllNum(start, i-1) * addAllNum(i+1, end);}return allNum;}
}

2 Java AC

/*** Definition for binary tree* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; left = null; right = null; }* }*/
public class Solution {public ArrayList<TreeNode> generateTrees(int n) {return dfs(1, n);}private ArrayList<TreeNode> dfs(int start, int end){ArrayList<TreeNode> numList = new ArrayList<TreeNode>();if (start > end) {TreeNode node = null;numList.add(node);return numList;}if (start == end) {TreeNode node = new TreeNode(start);numList.add(node);return numList;}for (int i = start; i <= end; i++) {TreeNode node = null;ArrayList<TreeNode> numList1 = dfs(start, i - 1);ArrayList<TreeNode> numList2 = dfs(i + 1, end);int size1 = numList1.size();int size2 = numList2.size();for (int j = 0; j < size1; j++) {for (int k = 0; k < size2; k++) {node = new TreeNode(i);node.left = numList1.get(j);node.right = numList2.get(k);numList.add(node);}}}return numList;}
}

这篇关于【LeetCode】Unique Binary Search Trees I II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---