gpt-4o-2024-08-06· OpenAI
WildChat-4.8M (AI2)
Give simple, common, and optimised Java solution /** * Definition for a binary tree…
- User
Give simple, common, and optimised Java solution
/**
- Definition for a binary tree node.
- public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode ) 1 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 generateTrees (int n) {
- Assistant
To generate all structurally unique BSTs that store values 1 through
n, you can use a recursive approach. Here's a simple, common, and optimized Java solution:import java.util.ArrayList; import java.util.List; public class TreeNode { int val; TreeNode left; TreeNode right; 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) { if (n == 0) { return new ArrayList<>(); } return generateTrees(1, n); } private List<TreeNode> generateTrees(int start, int end) { List<TreeNode> allTrees = new ArrayList<>(); if (start > end) { allTrees.add(null); return allTrees; } // Generate all combinations of BSTs for (int i = start; i <= end; i++) { // Generate all left and right subtrees List<TreeNode> leftTrees = generateTrees(start, i - 1); List<TreeNode> rightTrees = generateTrees(i + 1, end); // Combine them with the current node as root for (TreeNode left : leftTrees) { for (TreeNode right : rightTrees) { TreeNode currentTree = new TreeNode(i); currentTree.left = left; currentTree.right = right; allTrees.add(currentTree); } } } return allTrees; } }Explanation:
-
TreeNode Class: Defined with a value (
val), a left child (left), and a right child (right). -
generateTrees Method: Main method to call. It initiates the recursive tree generation starting from node
1ton. -
Recursive Logic:
- Base Case: If
startis greater thanend, return a list containingnull. This handles the absence of nodes for subtrees. - Recursive Case:
- Iterate over each possible root node value (
ifromstarttoend). - Recursively generate all possible left subtrees from
starttoi-1. - Recursively generate all possible right subtrees from
i+1toend. - Combine each left and right subtree with the current node as a root and add the constructed tree to the list.
- Iterate over each possible root node value (
- Base Case: If
This solution uses recursion and backtracking to explore all possible combinations of unique BSTs.
-