Dual LinkedList and BFS, 4ms Java Solution


  • 0
    J

    Code as below, should be easy to understand

    public class Solution {
        private class Node {
            private List<Integer> list=new ArrayList<>();
            private Node pre=null;
            private Node next=null;
        }
        public List<List<Integer>> verticalOrder(TreeNode root) {
            List<List<Integer>> res=new ArrayList<>();
            if (root==null) return res;
            Node p=new Node();
            Queue<TreeNode> q1=new LinkedList<>();
            Queue<Node> q2=new LinkedList<>();
            q1.offer(root);
            q2.offer(p);
            while (!q1.isEmpty()) {
                TreeNode x=q1.poll();
                Node y=q2.poll();
                y.list.add(x.val);
                if (x.left!=null) {
                    if (y.pre==null) {
                        Node pre=new Node();
                        pre.next=y;
                        y.pre=pre;
                    }
                    q1.offer(x.left);
                    q2.offer(y.pre);
                }
                if (x.right!=null) {
                    if (y.next==null) {
                        Node next=new Node();
                        y.next=next;
                        next.pre=y;
                    }
                    q1.offer(x.right);
                    q2.offer(y.next);
                }
            }
            while (p.pre!=null) p=p.pre;
            while (p!=null) {
                res.add(p.list);
                p=p.next;
            }
            return res;
        }
    }

Log in to reply
 

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