JAVA DP Solution and Brute Force Recursive Solution.


  • 38
    J

    The first method that came to mind was the brute force solution as below.

     public List<TreeNode> generateTrees(int n) {
         return generateTrees(1,n);
     }
    
    public List<TreeNode> generateTrees(int start,int end){             
        List<TreeNode> trees = new ArrayList<TreeNode>();
        if(start>end){  trees.add(null); return trees;}
    
        for(int rootValue=start;rootValue<=end;rootValue++){
            List<TreeNode> leftSubTrees=generateTrees(start,rootValue-1);
            List<TreeNode> rightSubTrees=generateTrees(rootValue+1,end);
    
            for(TreeNode leftSubTree:leftSubTrees){
                for(TreeNode rightSubTree:rightSubTrees){
                    TreeNode root=new TreeNode(rootValue);
                    root.left=leftSubTree;
                    root.right=rightSubTree;
                    trees.add(root);
                }
            }
        }
        return trees;
    }
    

    Then @6219221 reminded me it is unnecessary to create the BSTs with all brand new nodes.
    Assume you have a list of all BSTs with values from 1 to n-1, every possible way to insert value n only involves changing the right tree (root inclusive) because n is always greater than root.val and the left subtree structure is fixed. So all we gotta do is to create a new copy of the right part of the tree and point the new root.left to the original left subtree. This way we reuse the left tree, which saves time and space.

    How to insert Node n into the right subtree?
    Given any BST on the n - 1 level, it will be only valid to put n on the root.right, root.right.right or root.right.....right locations and then move the right subtree of n.right...right to become the left child of n, in order to keep n on the right-most position as the greatest value in the tree.

    Here is my implementation. Note that I do the dp from [n] back to [n to 1]. Therefore all the right subtree structures are fixed and new values are inserted into the left side, opposite to making BSTs from 1 to [1 to n].

        public List<TreeNode> generateTrees(int n) {
            List<TreeNode> res = new ArrayList<>();
            res.add(null);
            for(; n > 0; n--) {
                List<TreeNode> next = new ArrayList<>();
                for(TreeNode node: res) {
                    //the special case when Node(n) is root of new tree
                    TreeNode root = new TreeNode(n); 
                    root.right = node;
                    next.add(root);
                   //while loop inserts new value to every possible position into the left tree side
                    while(node != null) {
                        TreeNode cRoot = new TreeNode(root.right.val);
                        //clone left subtree
                        cRoot.left = copyTree(root.right.left);
                        //reusing - point new root.right to the original right subtree
                        cRoot.right = root.right.right;
                        //curr is the cutoff node whose right child will be replaced by the new n 
                        TreeNode curr = getValNode(cRoot, node.val); 
                        //place n as curr's right child, make curr's original right child as the left child of n.
                        TreeNode tmp = curr.left;
                        curr.left = new TreeNode(n);
                        curr.left.right = tmp;
    
                        next.add(cRoot);
                        node = node.left;
                    }
                }
                res = next;
            }
            return res;
        }
        private TreeNode getValNode(TreeNode n, int val) { //find the cutoff node in the new tree
            while(n != null) {
                if(n.val == val) break;
                n = n.left;
            }
            return n;
        }
    
        private TreeNode copyTree(TreeNode root) { //clone the right subtree
            if(root == null) return null;
            TreeNode cRoot = new TreeNode(root.val);
            cRoot.left = copyTree(root.left);
            cRoot.right = copyTree(root.right);
            return cRoot;
        }

  • 0
    R

    Hi, this is my code in C++ but it is wrong, with the same idea as yours, can you tell me what is my mistake?

    typedef TreeNode Node;
    
        class Solution {
        public:
            vector<TreeNode*> generateTrees(int n) {
                return generateTrees(1,n);
            }
        private:
            vector<Node*> generateTrees(int minV, int maxV) {
                if(minV > maxV)
                    return vector<Node*>{NULL};
                
                vector<Node*> trees;
                for(int i=minV; i<=maxV; ++i) {
                    vector<Node*> left=  generateTrees(minV, i-1);
                    vector<Node*> right= generateTrees(i+1, maxV);
                    Node* root=new Node(i);
                    for(int l=0; l<left.size(); ++l){
                        for(int r=0; r<right.size(); ++r){
                            root->left=left[l];
                            root->right=right[r];
                            trees.push_back(root);
                        }
                    }
                }
                return trees;
            }
        };
    

  • 1
    W

    ur problem might be on how u deal with the base case


  • 0
    H

    You problem is that you are creating 'root' node just once but you have to create it each time you iterate the left and right subtrees.
    Move Node* root=new Node(i); line in inner loop :for(int r=0; r<right.size(); ++r)


  • 0
    T

    @homerhickam
    Hi , I met the same mistakes. But I really don't know why I should create the new root node in each iteration? Could you explain it ?


  • 1
    W

    @TylerZhang I think the reason is that the TreeNode object is mutable. If you do not create a new root every time, all root nodes in the "trees" point to the last tree. It is like this: suppose you already have trees = [root]. After another iteration, root will be overwritten by new left and right children, that is, the root already in your "trees" will change as well, and then you push this root to your "trees". Finally, all roots in trees are the same.


  • 0
    A

    Hi, your solution is not a DP. So there will exist so many duplicate trees created during the recursion, which will waste too much time.


  • 0
    J
    This post is deleted!

  • 0
    J
    This post is deleted!

  • 0
    J

    @a6219221
    Oh yes. It took me a while to see what you are saying. Subtrees could be reused with the DP approach. Not only it saves time but also space is freed from creating extra nodes of the same value. Although having trees that share branches could be tricky to deal with in the real world, it is the best solution for an algorithm exercise indeed.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.