My Java solution in DP method


  • 1
    G
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public static List<TreeNode> generateTrees(int n) {
    		List<List<TreeNode>> list = new ArrayList<List<TreeNode>>();
    		ArrayList o = new ArrayList<TreeNode>();
    		list.add(o);
    		o.add(null);
    		TreeNode temp = new TreeNode(1);
    		ArrayList<TreeNode> part = new ArrayList<TreeNode>();
    		part.add(temp);
    		list.add(part);
    		for(int i=2;i<=n;i++){
    			part = new ArrayList<TreeNode>();
    			for(int j=1;j<=i;j++){
    				for(int m=0;m<list.get(j-1).size();m++){
    					for(int k=0;k<list.get(i-j).size();k++){
    						TreeNode temp1 = new TreeNode(j);
    						temp1.left = list.get(j-1).get(m);
    						int val = j;
    						temp1.right = search(list.get(i-j).get(k),val);
    						part.add(temp1);
    					}
    				}
    			}
    			list.add(part);
    		}
    		return list.get(n);
        }
    	
    	public static TreeNode search(TreeNode root,int val){
    		if(root==null)return null;
    		TreeNode result = new TreeNode(root.val+val);
    		result.left = search(root.left,val);
    		result.right = search(root.right,val);
    		return result;
    	}
    }

Log in to reply
 

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