Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/95.html
Given an integer n
, return all the structurally unique BST's (binary search trees), which has exactly n
nodes of unique values from 1
to n
. Return the answer in any order.
Example 1:
Input: n = 3 Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
Example 2:
Input: n = 1 Output: [[1]]
Constraints:
1 <= n <= 8
Algorithm
This kind of tree building problem is generally solved by recursion
, and this problem is no exception, dividing the left and right subtrees, and recursive construction.
This actually uses the well-known divide and conquer method Divide and Conquer, and similar problems are the same as the previous Different Ways to Add Parentheses
method, using recursion to solve, dividing the left and right sub-arrays, recursive construction.
At the beginning, consider the interval [1, n]
as a whole, and then you need to treat each number as the root node, which divides the left and right sub-intervals, and then call the recursive function separately, you will get two Node array, the next thing to do is to take one node each time from these two arrays, as the left and right child nodes of the current root node, and then add the root node to the result array.
Pitfalls
-
When
start>end
, if you directly return an empty list, size=0, then inserting the left and right subtrees will not work,i=0, i<left.size()
loop will not enter So I use if-else to determine whether the list is empty So you must add a null to the list, let size=1 -
To create a root node, it must be in two for loops, because each time is an independent tree. I created the root node first, and then went into the for loop, but the result was repeated, because each for was operated on the same tree, and the added tree was changed.
I thought of the idea of creating left and right subtrees, but I didn’t figure out how to implement it and how to return the built subtrees to the upper level. This generate(start, end)
is great.
Code
-
import java.util.ArrayList; import java.util.List; public class Unique_Binary_Search_Trees_II { public static void main(String[] args) { Unique_Binary_Search_Trees_II out = new Unique_Binary_Search_Trees_II(); Solution s = out.new Solution(); for (TreeNode each: s.generateTrees(3)) { System.out.println(each); } } /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ // optimized public class Solution { public List<TreeNode> generateTrees(int n) { if (n == 0) { return new ArrayList<TreeNode>(); } return generate(1, n); } public ArrayList<TreeNode> generate(int start, int end) { ArrayList<TreeNode> result = new ArrayList<TreeNode>(); if (start > end) { result.add(null); // @note:@memorize:这里就是空的左树或者右树,是关键 return result; } for (int i = start; i <= end; i++) { // i as root ArrayList<TreeNode> left = generate(start, i - 1); ArrayList<TreeNode> right = generate(i + 1, end); // append left subtree and right subtree // @note@note: should put inside for looping!, or, reference is modified onstantly! for (TreeNode l : left) { for (TreeNode r : right) { // 每次都要复制一个 TreeNode currentRoot = new TreeNode(i); // 当前的i作为head node currentRoot.left = l; currentRoot.right = r; result.add(currentRoot); } } } return result; } } // DP version public class Solution_iterative { public List<TreeNode> generateTrees(int n) { if (n == 0) { return new ArrayList<TreeNode>(); } @SuppressWarnings("unchecked") List<TreeNode>[] result = new ArrayList[n + 1]; // @note: just like: new int[10] result[0] = new ArrayList<TreeNode>(); // empty tree result[0].add(null); for (int i = 1; i <= n; i++) { result[i] = new ArrayList<TreeNode>(); // store all combinations when n is i for (int leftIndex = 0; leftIndex < i; leftIndex++) { for (TreeNode leftSub : result[leftIndex]) { // get ONE left subtree for (TreeNode rightSub : result[i - leftIndex - 1]) { // get One right subtree TreeNode tmpRoot = new TreeNode(leftIndex + 1); tmpRoot.left = leftSub; // @note:@memorize: key is here. should generate right subtree, where the start number is "1 + leftIndex" tmpRoot.right = clone(rightSub, leftIndex + 1); result[i].add(tmpRoot); } } } } return result[n]; } // apply offset is still a local recursion private TreeNode clone(TreeNode n, int offset) { // name is nice, self-explanatory if (n == null) return null; TreeNode node = new TreeNode(n.val + offset); node.left = clone(n.left, offset); node.right = clone(n.right, offset); return node; } } } ############ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public List<TreeNode> generateTrees(int n) { return generateTrees(1, n); } private List<TreeNode> generateTrees(int left, int right) { List<TreeNode> ans = new ArrayList<>(); if (left > right) { ans.add(null); } else { for (int i = left; i <= right; ++i) { List<TreeNode> leftTrees = generateTrees(left, i - 1); List<TreeNode> rightTrees = generateTrees(i + 1, right); for (TreeNode l : leftTrees) { for (TreeNode r : rightTrees) { TreeNode node = new TreeNode(i, l, r); ans.add(node); } } } } return ans; } }
-
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def generateTrees(self, n: int) -> List[TreeNode]: def gen(left, right): ans = [] # this if check instead of if left==right then return Node(left), less hassle if left > right: ans.append(None) else: # right+1, to cover case when left==right for i in range(left, right + 1): left_trees = gen(left, i - 1) right_trees = gen(i + 1, right) for l in left_trees: for r in right_trees: node = TreeNode(i, l, r) ans.append(node) return ans return gen(1, n) ############ class Solution(object): def generateTrees(self, n): """ :type n: int :rtype: List[TreeNode] """ def clone(root, offset): if root: newRoot = TreeNode(root.val + offset) left = clone(root.left, offset) right = clone(root.right, offset) newRoot.left = left newRoot.right = right return newRoot if not n: return [] dp = [[]] * (n + 1) dp[0] = [None] for i in range(1, n + 1): dp[i] = [] for j in range(1, i + 1): for left in dp[j - 1]: for right in dp[i - j]: root = TreeNode(j) root.left = left root.right = clone(right, j) dp[i].append(root) return dp[-1]
-
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<TreeNode*> generateTrees(int n) { return gen(1, n); } vector<TreeNode*> gen(int left, int right) { vector<TreeNode*> ans; if (left > right) { ans.push_back(nullptr); } else { for (int i = left; i <= right; ++i) { auto leftTrees = gen(left, i - 1); auto rightTrees = gen(i + 1, right); for (auto& l : leftTrees) { for (auto& r : rightTrees) { TreeNode* node = new TreeNode(i, l, r); ans.push_back(node); } } } } return ans; } };
-
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func generateTrees(n int) []*TreeNode { var gen func(left, right int) []*TreeNode gen = func(left, right int) []*TreeNode { var ans []*TreeNode if left > right { ans = append(ans, nil) } else { for i := left; i <= right; i++ { leftTrees := gen(left, i-1) rightTrees := gen(i+1, right) for _, l := range leftTrees { for _, r := range rightTrees { node := &TreeNode{i, l, r} ans = append(ans, node) } } } } return ans } return gen(1, n) }
-
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function generateTrees(n: number): Array<TreeNode | null> { if (n == 0) return []; return helper(1, n); } function helper(start: number, end: number): Array<TreeNode | null> { let ans = []; if (start > end) { ans.push(null); return ans; } for (let i = start; i <= end; i++) { let lefts = helper(start, i - 1); let rights = helper(i + 1, end); for (let left of lefts) { for (let right of rights) { let root = new TreeNode(i, left, right); ans.push(root); } } } return ans; }