Straight Forward appending right to left list (without range computation)


  • 0
    I

    I tried to find a similar approach in other's solutions but couldn't. (Let me know if I missed any)

    Short description

    1. Use two list: LeftList and RightList
    2. Append the node value to either LeftList or RightList according to an offset (centered at root)
    3. When BFS is done, append RightList to reversed LeftList
    4. Return LeftList

    public class Solution {

        public List<List<Integer>> verticalOrder(TreeNode root) {
            if(root == null) return new ArrayList<List<Integer>>();
            
            List<List<Integer>> left = new ArrayList<>();
            List<List<Integer>> right = new ArrayList<>();
            verticalOrder(root, left, right);
            Collections.reverse(left);
            left.addAll(right);
            return left;
        }
        
        public void verticalOrder(TreeNode root, List<List<Integer>> left, List<List<Integer>> right) {
            // do BFS
            
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            Queue<Integer> offsetQ = new LinkedList<Integer>();
            
            queue.add(root);
            offsetQ.add(0);
            
            int offset;
            List<Integer> list;
            while(!queue.isEmpty()) {
                TreeNode node = queue.poll();
                offset = offsetQ.poll();
                
                if(offset < 0) { // left subtrees
                    if(left.size() < -offset) left.add(new ArrayList<Integer>());
                    list = left.get(-offset-1);
                } else { // root and right subtrees
                    if(right.size() < offset+1)  right.add(new ArrayList<Integer>());
                    list = right.get(offset);
                }
    
                list.add(node.val);
    
                if(node.left != null) {
                    queue.add(node.left);
                    offsetQ.add(offset-1);
                }
                if(node.right != null) {
                    queue.add(node.right);
                    offsetQ.add(offset+1);
                }
            }
        }
        
        
    }

Log in to reply
 

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