BFS&DFS Java solution using predefined class instead of two queues


  • 0

    BFS solution

    class Node{
            private TreeNode node;
            private int pos;
            public Node(TreeNode node, int pos){
                this.node = node;
                this.pos = pos;
            }
        }
        public List<List<Integer>> verticalOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            if(root == null) return res;
            int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
            HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
            Queue<Node> q = new LinkedList<Node>();
            q.offer(new Node(root, 0));
            while(!q.isEmpty()){
                Node cur = q.poll();
                TreeNode node = cur.node;
                int pos = cur.pos;
                if(!map.containsKey(pos))
                    map.put(pos, new ArrayList<Integer>());
                map.get(pos).add(node.val);
                min = Math.min(min, pos);
                max = Math.max(max, pos);
                if(node.left != null) q.offer(new Node(node.left, pos - 1));
                if(node.right != null) q.offer(new Node(node.right, pos + 1));
            }
            for(int i = min; i <= max; i ++){
                res.add(new ArrayList<Integer>(map.get(i)));
            }
            return res;
        }
    

    DFS
    The DFS solution cannot get AC with the test case [3,9,8,4,0,1,7,null,null,null,2,5]
    The expected output should be [[4],[9,5],[3,0,1],[8,2],[7]] while mine is [[4],[9,5],[3,0,1],[2,8],[7]]. I see the difference but dont quite understand why the sequence of output brings fault.

    class Node{
            private TreeNode node;
            private int pos;
            public Node(TreeNode node, int pos){
                this.node = node;
                this.pos = pos;
            }
        }
        public List<List<Integer>> verticalOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            if(root == null) return res;
            int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
            HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
            Queue<Node> q = new LinkedList<Node>();
            q.offer(new Node(root, 0));
            while(!q.isEmpty()){
                Node cur = q.poll();
                TreeNode node = cur.node;
                int pos = cur.pos;
                if(!map.containsKey(pos))
                    map.put(pos, new ArrayList<Integer>());
                map.get(pos).add(node.val);
                min = Math.min(min, pos);
                max = Math.max(max, pos);
                if(node.left != null) q.offer(new Node(node.left, pos - 1));
                if(node.right != null) q.offer(new Node(node.right, pos + 1));
            }
            for(int i = min; i <= max; i ++){
                res.add(new ArrayList<Integer>(map.get(i)));
            }
            return res;
        }
    

    Hope it helps.


Log in to reply
 

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