Medium Unique Binary Search Trees II
31%
Accepted
Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.
Have you met this question in a real interview?
Yes
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
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @paramn n: An integer * @return: A list of root */ public List<TreeNode> generateTrees(int n) { // write your code here return generating(1, n); } private List<TreeNode> generating(int left, int right){ List<TreeNode> result = new ArrayList<TreeNode>(); if(left > right){ result.add(null); return result; } if(left == right){ result.add(new TreeNode(left)); return result; } for(int i = left; i <= right; i++){ for(TreeNode l : generating(left, i-1)){ for(TreeNode r : generating(i+1, right)){ TreeNode node = new TreeNode(i); node.left = l; node.right = r; result.add(node); } } } return result; } }
No comments:
Post a Comment