Java 2ms efficient DP heuristic solution


  • 0
    P

    The general DP way of solving this problem is construct the tree from 0, 1, 2 .. until n nodes. The keys is: there are only three ways to add new node with higher value on top of all the current trees with lower value. Details are explained in comments.

        public List<TreeNode> generateTrees(int n) {
            ArrayList<TreeNode> nodes = new ArrayList<>();
            if (n == 0) return nodes;
            nodes.add(new TreeNode(1));
            for (int i = 2; i <= n; i++){
                ArrayList<TreeNode> newNodes = new ArrayList<>();
                for (TreeNode treeNode: nodes){
                    // 1. Add new node on right top of original tree
                    TreeNode newRoot = new TreeNode(i);
                    newRoot.left = copyTreeNode(treeNode);
                    newNodes.add(newRoot);
                    TreeNode nextRoot = treeNode;
    
                    // 2. Add new node on all most right edges of the original tree
                    while (nextRoot.right != null){
                        TreeNode next = copyTreeNode(treeNode);
                        newNodes.add(next);
                        // find the current right edge in the newly copied tree
                        while (next.val != nextRoot.val){
                            next = next.right;
                        }
                        
                        TreeNode breakNode = new TreeNode(i);
                        breakNode.left = next.right;
                        next.right = breakNode;
                        // next right edge
                        nextRoot = nextRoot.right;
                    }
    
                    // 3. Add new node on the most right-bottom of original tree
                    nextRoot.right = new TreeNode(i);
                }
                nodes.addAll(newNodes);
            }
            return nodes;
        }
    
        private TreeNode copyTreeNode(TreeNode treeNode){
            if (treeNode == null) return null;
            TreeNode newNode = new TreeNode(treeNode.val);
            newNode.left = copyTreeNode(treeNode.left);
            newNode.right = copyTreeNode(treeNode.right);
            return newNode;
        }
    

Log in to reply
 

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