Skip to content
TheChatArchiveThe Chat Archive
gpt-4o-2024-08-06· OpenAIAi2 WildChat-4.8M (AI2)

Give simple, common, and optimised Java solution /** * Definition for a binary tree…

  1. 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) {
  2. 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 1 to n.

    • Recursive Logic:

      • Base Case: If start is greater than end, return a list containing null. This handles the absence of nodes for subtrees.
      • Recursive Case:
        • Iterate over each possible root node value (i from start to end).
        • Recursively generate all possible left subtrees from start to i-1.
        • Recursively generate all possible right subtrees from i+1 to end.
        • Combine each left and right subtree with the current node as a root and add the constructed tree to the list.

    This solution uses recursion and backtracking to explore all possible combinations of unique BSTs.