wrong result?


  • 0
    J

    for test:
    [-64,12,18,-4,-53,null,76,null,-51,null,null,-93,3,null,-31,47,null,3,53,-81,33,4,null,-51,-44,-60,11,null,null,null,null,78,null,-35,-64,26,-81,-31,27,60,74,null,null,8,-38,47,12,-24,null,-59,-49,-11,-51,67,null,null,null,null,null,null,null,-67,null,-37,-19,10,-55,72,null,null,null,-70,17,-4,null,null,null,null,null,null,null,3,80,44,-88,-91,null,48,-90,-30,null,null,90,-34,37,null,null,73,-38,-31,-85,-31,-96,null,null,-18,67,34,72,null,-17,-77,null,56,-65,-88,-53,null,null,null,-33,86,null,81,-42,null,null,98,-40,70,-26,24,null,null,null,null,92,72,-27,null,null,null,null,null,null,-67,null,null,null,null,null,null,null,-54,-66,-36,null,-72,null,null,43,null,null,null,-92,-1,-98,null,null,null,null,null,null,null,39,-84,null,null,null,null,null,null,null,null,null,null,null,null,null,-93,null,null,null,98]

    there's one column, my answer is
    [3,-44,-60,12,-51,-59,67,-88,48,-26,92,72]
    the expected answer is:
    [3,-44,-60,12,-59,-51,67,-88,48,-26,92,72]

    seems mine is correct, expected answer is wrong.


  • 0
    J

    post my code here. basically BFS. Passed 211 of 212 tests. I believe one test case is wrong.

        public List<List<Integer>> verticalOrder(TreeNode root) {
            List<List<Integer>> result = new ArrayList<>();
            if (root == null) return result;
            HashMap<Integer, List<Integer>> map = new HashMap<>();
            HashMap<Integer, List<TreeNode>> level = new LinkedHashMap<>();
            ArrayList<TreeNode> nodeList = new ArrayList<>();
            nodeList.add(root);
            level.put(0, nodeList);
            while (!(level.size() == 0)) {
                HashMap<Integer, List<TreeNode>> nextLevel = new LinkedHashMap<>();
                for (Integer k : level.keySet()) {
                    List<TreeNode> nodes = level.get(k);
                    List<Integer> list = map.get(k);
                    if (list == null) {
                        list = new ArrayList<>();
                        map.put(k, list);
                    }
                    for (TreeNode node : nodes) {
                        list.add(node.val);
                        if (node.left != null) {
                            List<TreeNode> ls = nextLevel.get(k - 1);
                            if (ls == null) {
                                ls = new ArrayList<>();
                                nextLevel.put(k - 1, ls);
                            }
                            ls.add(node.left);
                        }
                        if (node.right != null) {
                            List<TreeNode> rs = nextLevel.get(k + 1);
                            if (rs == null) {
                                rs = new ArrayList<>();
                                nextLevel.put(k + 1, rs);
                            }
                            rs.add(node.right);
                        }
                    }
                }
                level = nextLevel;
            }
            Integer[] keys = new Integer[map.size()];
            keys = map.keySet().toArray(keys);
            Arrays.sort(keys);
            for (int k : keys) {
                result.add(map.get(k));
            }
            return result;
        }
        
    

Log in to reply
 

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