java DP solution


  • 0
    2
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        private List[] lists;
        public List<TreeNode> generateTrees(int n) {
            List<TreeNode> l = new ArrayList<TreeNode>();
            if (n == 0) {
                return l;
            }
            l.add(null);
            lists = new List[n + 1];
            lists[0] = l;
            for (int i = 1; i <= n; i++) {
                generate(i);
            }
            return (List<TreeNode>)lists[n];
        }
        private void generate(int n) {
            List<TreeNode> l = new ArrayList<TreeNode>();
            for (int i = 1; i <= n; i++) {
                for (TreeNode left : (List<TreeNode>)lists[i - 1]) {
                    for (TreeNode right : (List<TreeNode>)lists[n - i]) {
                        TreeNode root = new TreeNode(i);
                        root.left = copyAdd(left, 0);
                        root.right = copyAdd(right, i);
                        l.add(root);
                    }
                }
            }
            lists[n] = l;
        }
        private TreeNode copyAdd(TreeNode t, int val) {
            if (t == null) {
                return null;
            }
            TreeNode copy = new TreeNode(t.val + val);
            copy.left = copyAdd(t.left, val);
            copy.right = copyAdd(t.right, val);
            return copy;
        }
    }
    

Log in to reply
 

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