My AC Java Solution without recursive


  • 1
    C

    My answer is below, is it use DP? or can it be more effective?

    /**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; left = null; right = null; }
     * }
     */
    public class Solution {
        public List<TreeNode> generateTrees(int n) {
    		
    		//key为数字,value是1到数字key这个序列,可以生成的所有BST的根结点List
    		Map<Integer, List<TreeNode>> list = new HashMap<Integer, List<TreeNode>>();
    		List<TreeNode> temp0 = new ArrayList<TreeNode>();
            temp0.add(null);
    	    list.put(0, temp0);   //注意这里,当n为0时,依然需要创建temp0,只是temp0里面没有任何元素,也就是没有满足条件的BST
    	    
    	    if(n < 1)
    	    	return list.get(0);
    		
    	    List<TreeNode> temp1 = new ArrayList<TreeNode>();
            temp1.add(new TreeNode(1));
            list.put(1, temp1);
            
            for(int i = 2; i <= n; i++)
            {
                List<TreeNode> l = new ArrayList<TreeNode>();
                List<TreeNode> preL = list.get(i-1);  //想求f(n)要获得f(n-1)
                Iterator<TreeNode> it = preL.iterator();
                while(it.hasNext())
                {
                    TreeNode root = cloneTree(it.next());   //注意,这里要对树进行复制,要不然会直接修改f(n-1)里的树
                    TreeNode rootClone = cloneTree(root);   //克隆两次,一个是root用于第一种情况,另一个是rootClone用于第二种情况
                    l.add(constructTree(root, new TreeNode(i)));   //第一种情况:将i作为原来BST的最右结点
                    TreeNode node = new TreeNode(i);
                    node.left = rootClone;   //第二种情况:将原来的BST作为i的左子树
                    l.add(node);
                }
                for(int j = 1; j < i-1; j++)
                {
                    List<TreeNode> l1 = list.get(j);   //f(j)
                    List<TreeNode> l2 = list.get(i-j-1);   //f(i-j-1)
                    Iterator<TreeNode> it1 = l1.iterator();
                     
                    while(it1.hasNext())   //f(j)和f(i-j-1)两者相乘
                    {
                    	TreeNode node1 = it1.next();
                    	Iterator<TreeNode> it2 = l2.iterator();
                        while(it2.hasNext())
                        {
                        	TreeNode root1 = cloneTree(node1);   //克隆f(j)里的树
                            TreeNode root2 = changeData(cloneTree(it2.next()), j);   //先克隆f(i-j-1)里的树,然后改变root2里结点的值
                            TreeNode node = new TreeNode(i);
                            TreeNode root3 = constructTree(root1, node);   //将i连接进root1
                            node.left = root2;   //连接node和root2,即:将i的左子树赋为root2
                            l.add(root3);
                        }
                    }
                }
                list.put(i, l);
            }
            
            return list.get(n);
        }
        
        //将结点node插入树root中,满足node是root中最右边的结点,即满足node是中序遍历时最后一个结点
        public TreeNode constructTree(TreeNode root, TreeNode node) {
        	TreeNode temp = root;
        	TreeNode preTemp = null;
        	while(temp != null)
        	{
        		preTemp = temp;
        		temp = temp.right;
        	}
        	if(preTemp != null)
        		preTemp.right = node;
        	
            return root;
        }
        
        public TreeNode cloneTree(TreeNode root) {   //克隆树
        	TreeNode rootClone = new TreeNode(root.val);
        	if(root.left != null)
        		rootClone.left = cloneTree(root.left);
        	if(root.right != null)
        		rootClone.right = cloneTree(root.right);
        	return rootClone;
        }
        
        public TreeNode changeData(TreeNode root, int diff) {   //改变树中结点的值,每个结点的值增大diff
        	root.val += diff;
        	if(root.left != null)
        		changeData(root.left, diff);
        	if(root.right != null)
        		changeData(root.right, diff);
            return root;
        }
    }

Log in to reply
 

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