211/212 testcases passed. Don't know what's wrong with the code


  • 0
    public List<List<Integer>> verticalOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
             if(root == null)
                return res;
             List<Node> nodes = new ArrayList<Node>();
             Node node = new Node(root.val,0,0,true);
             nodes.add(node);
             preorder(root,nodes, 0,0);
             Collections.sort(nodes);
             int span = Integer.MAX_VALUE;
             for(int i=0; i < nodes.size(); i++){
                 if(nodes.get(i).span != span){
                     List<Integer> list = new ArrayList<Integer>();
                     res.add(list);
                     span = nodes.get(i).span;
                 }
                res.get(res.size()-1).add(nodes.get(i).val);
             }
             return res;
        }
        void preorder(TreeNode root,  List<Node> nodes,int span, int height){
            if(root.left != null){
                Node node = new Node(root.left.val,span-1,height+1,true);
                nodes.add(node);
               preorder(root.left,nodes,span-1,height+1); 
            }
            if(root.right != null){
                Node node = new Node(root.right.val,span+1,height+1,false);
                nodes.add(node);
                preorder(root.right,nodes,span+1,height+1);
            }
        }
        private static class Node implements Comparable<Node>{
            int span;
            int height;
            boolean left;
            int val;
            Node(int val, int span, int height, boolean left){
                this.val = val;
                this.span = span;
                this.height = height;
                this.left = left;
            }
            public int compareTo(Node node){
                if(this.span != node.span)
                   return this.span - node.span;
                if(this.height != node.height)
                   return this.height - node.height;
                if(this.left)
                  return 1;
                return -1;  
            }
        }
    
    The code is based on simple sorting of all the tree nodes based on level and span(its position from left). It passes 211 testcases out of 212. I can't get it working for last testcase..
    Any help is really appreciated. Thanks in advance.
    
    
    
    

Log in to reply
 

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