Using Doubly Linked List and BFS without HashMap


  • 0
    Z
    class DBNode{
        ArrayList<Integer> list;
        DBNode pre;
        DBNode next;
        DBNode(){
            this.list = new ArrayList<Integer>();
            this.pre = null;
            this.next = null;
        }
    } 
    
    public class Solution {
        public List<List<Integer>> verticalOrder(TreeNode root) {
            // define result
            List<List<Integer>> rst = new ArrayList<List<Integer>>();
            // check input
            if(root == null){
                return rst;
            }
            // Using Doubly Linked List to Implement BFS
            DBNode start = new DBNode();
            Queue<DBNode> queue = new LinkedList<DBNode>();
            Queue<TreeNode> tqueue = new LinkedList<TreeNode>();
            queue.offer(start);
            tqueue.offer(root);
            while(!queue.isEmpty()){
                DBNode temp = queue.poll();
                TreeNode ttemp = tqueue.poll();
                temp.list.add(ttemp.val);
                if(ttemp.left != null){
                    if(temp.pre == null){
                        start = new DBNode();
                        start.next = temp;
                        temp.pre = start;
                    }
                    queue.offer(temp.pre);
                    tqueue.offer(ttemp.left);
                }
                if(ttemp.right != null){
                    if(ttemp.right != null){
                        if(temp.next == null){
                            DBNode next = new DBNode();
                            next.pre = temp;
                            temp.next = next;
                        }
                        queue.offer(temp.next);
                        tqueue.offer(ttemp.right);
                    }
                }
            }
            while(start != null){
                rst.add(start.list);
                start = start.next;
            }
            
            return rst;
        }
    }
    
    

Log in to reply
 

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