3ms 100% Only Using A BFS Queue


  • 3
    O

    BFS computes each nodes "offset" with respect to root so that each node will know it's index in the output list.

    public List<List<Integer>> verticalOrder(TreeNode root) {
        ArrayList<TreeNode> q = new ArrayList();
        ArrayList<Integer> ofst = new ArrayList();
        List<List<Integer>> ans = new ArrayList();
        if (root == null) return ans;
        int bdMin = 0, bdMax = 0, i = 0;
        q.add(root); 
        ofst.add(0);
        for (; i < q.size(); i++) {
            int y = ofst.get(i);
            TreeNode r = q.get(i);
            bdMin = Math.min(bdMin, y); bdMax = Math.max(bdMax, y);
           
            if (r.left != null) {
                q.add(r.left);
                ofst.add(y - 1);
            }
            if (r.right != null) {
                q.add(r.right);
                ofst.add(y + 1);
            }
        }
        
        int m = bdMax - bdMin + 1;
        for (i = 0; i < m; i++) ans.add(new ArrayList());
        for (i = 0; i < q.size(); i++)
            ans.get(ofst.get(i) - bdMin).add(q.get(i).val);
        
        return ans;
    }

Log in to reply
 

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