Tree Level-order Traversal

102. Binary Tree Level Order Traversal

class Solution {
    //BFS 最要在Node进入queue前就进行非空判断，使得进入queue的node本身都非null
    public List<List<Integer>> levelOrder(TreeNode root) {
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        
        if(root == null) return result;
        
        queue.offer(root);
        while(!queue.isEmpty()) {
            int num_on_level = queue.size();
            List<Integer> cur_result = new LinkedList<Integer>();
            for(int i = 0; i < num_on_level; i++) {
                TreeNode cur = queue.poll();
                if(cur.left != null) queue.add(cur.left);
                if(cur.right != null) queue.add(cur.right);
                cur_result.add(cur.val);
            }
            result.add(cur_result);
        }
        return result;
    }
}

103. Binary Tree Zigzag Level Order Traversal

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        
        if(root == null) return result;
        
        boolean order = true;
        queue.offer(root);
        while(!queue.isEmpty()) {
            int num_on_level = queue.size();
            List<Integer> cur_result = new LinkedList<Integer>();
            for(int i = 0; i < num_on_level; i++) {
                TreeNode cur = queue.poll();
                if(cur.left != null) queue.add(cur.left);
                if(cur.right != null) queue.add(cur.right);
                
                // add result to cur_result
                if(order) cur_result.add(cur.val);
                else cur_result.add(0, cur.val);   
            }
            result.add(cur_result);
            order = order ? false : true;
        }
        return result;
    }
}

107. Binary Tree Level Order Traversal II

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        
        if(root == null) return result;
        
        queue.offer(root);
        while(!queue.isEmpty()) {
            int num_on_level = queue.size();
            List<Integer> cur_result = new LinkedList<Integer>();
            for(int i = 0; i < num_on_level; i++) {
                TreeNode cur = queue.poll();
                if(cur.left != null) queue.add(cur.left);
                if(cur.right != null) queue.add(cur.right);
                cur_result.add(cur.val);
            }
            result.add(0, cur_result);
        }
        return result;
    }
}

515. Find Largest Value in Each Tree Row

class Solution {
    //BFS 最要在Node进入queue前就进行非空判断，使得进入queue的node本身都非null
    public List<Integer> largestValues(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<Integer> result = new LinkedList<Integer>();
        
        if(root == null) return result;
        
        queue.offer(root);
        while(!queue.isEmpty()) {
            int largest_elem = Integer.MIN_VALUE;
            int num_on_level = queue.size();
            for(int i = 0; i < num_on_level; i++) {
                TreeNode cur = queue.poll();
                largest_elem = Math.max(largest_elem, cur.val);
                if(cur.left != null) queue.add(cur.left);
                if(cur.right != null) queue.add(cur.right);
            }
            result.add(largest_elem);
        }
        
        return result;
    }
}