An iterative solution in JAVA, is it correct?


  • -2
    J

    Generate from 1 to n and build ith iteration based on (i-1)th trees.

    Basically given node i is the largest node so far, for each (i-1)th subtree:

    • add node i at root and attach (i-1)th trees to its left
    • find the largest node in (i-1)th trees, add node i to its right
    • find the largest node in (i-1)th trees, add it to node i's right, and add node i to its parent's right
    • handle duplicated case when the largest node in (i-1)th trees is root

    It didn't pass OJ at n=4 but I checked the result is correct except for the ordering in the sequence.

    Is it correct for n>4? and How to analyze the time complexity?

    public class Solution {
        public List<TreeNode> generateTrees(int n) {
            List<TreeNode> res = new ArrayList<TreeNode>();
            TreeNode newNode = null;
            if(n<=0){
                res.add(newNode);
                return res;
            }
            for(int i = 1; i <= n; i++){
                int size = res.size();
                if(size==0){
                    newNode = new TreeNode(i);
                    res.add(newNode);
                }else{
                    for(int j = 0; j < size; j++){
                        TreeNode prev = res.remove(0);
                        TreeNode curr;
                        curr = addToMaxBelow(i, prev);
                        if(curr!=null) res.add(curr);
                        curr = addToMaxAbove(i, prev);
                        if(curr!=null) res.add(curr);
                        curr = addToRoot(i, prev);
                        if(curr!=null) res.add(curr);
                    }
                }
            }
            return res;
        }
        
        private TreeNode addToMaxBelow(int i, TreeNode prev){
            TreeNode newNode = new TreeNode(i);
            TreeNode prevRoot = copyTree(prev);
            TreeNode max = getMax(prevRoot);
            if(max==null) return null;
            max.right = newNode;
            return prevRoot;
        }
        
        private TreeNode addToMaxAbove(int i, TreeNode prev){
            TreeNode newNode = new TreeNode(i);
            TreeNode prevRoot = copyTree(prev);
            TreeNode maxParent = getMaxParent(prevRoot);
            if(maxParent==null) return null;
            newNode.left = maxParent.right;
            maxParent.right = newNode;
            return prevRoot;
        }
        
        private TreeNode addToRoot(int i, TreeNode prev){
            TreeNode newNode = new TreeNode(i);
            TreeNode prevRoot = copyTree(prev);
            newNode.left = prevRoot;
            return newNode;
        }
        
        private TreeNode getMax(TreeNode root){
            if(root==null) return root;
            TreeNode curr = root;
            while(curr.right!=null){
                curr = curr.right;
            }
            return curr;
        }
        
        private TreeNode getMaxParent(TreeNode root){
            if(root==null) return root;
            TreeNode prev = null;
            TreeNode curr = root;
            while(curr.right!=null){
                prev = curr;
                curr = curr.right;
            }
            return prev;
        }
        
        private TreeNode copyTree(TreeNode root){
            if(root==null) return null;
            TreeNode newRoot = new TreeNode(root.val);
            newRoot.left = copyTree(root.left);
            newRoot.right = copyTree(root.right);
            return newRoot;
        }
    }

Log in to reply
 

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