Verbose Java Solution, Binary tree level order traversal, again.


  • 6

    Alright, two binary tree level order traversal problems in one contest. This time, mission is to find the max of each level...

    public class Solution {
        public int[] findValueMostElement(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            if (root == null) return new int[0];
            
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            
            while (!queue.isEmpty()) {
                int size = queue.size();
                int max = Integer.MIN_VALUE;
                for (int i = 0; i < size; i++) {
                    TreeNode node = queue.poll();
                    max = Math.max(max, node.val);
                    if (node.left != null) queue.add(node.left);
                    if (node.right != null) queue.add(node.right);
                }
                res.add(max);
            }
            
            int[] result = new int[res.size()];
            for (int i = 0; i < res.size(); i++) {
                result[i] = res.get(i);
            }
            
            return result;
        }
    }
    

  • 0
    N

    Hi @shawngao , Thanks for sharing the solution. Just wonder what's the space complexity of this solution. Is it O(n) since the worst case we have only 1 node we will need to add it to the queue? Thanks.


  • 0

    @ning2016 Yes. Both runtime and space complexity are O(n).


  • 0

    Similar solution, but separated level traversal from max logic:

    public class Solution {
      public List<Integer> largestValues(TreeNode root) {
        List<Integer> results = new ArrayList<>();
        levelTraversal(root, level -> results.add(Collections.max(level)));
        return results;
      }
      private void levelTraversal(TreeNode root, Consumer<List<Integer>> consumer) {
        List<Integer> level = new LinkedList<Integer>();
        for (Queue<TreeNode> queue = new LinkedList<>(Arrays.asList(root, null)); root != null && !queue.isEmpty(); ) {
          TreeNode next = queue.remove();
          if (next == null) {
            consumer.accept(level);
            level.clear();
            if (!queue.isEmpty())
              queue.add(null);
          } else {
            level.add(next.val);
            if (next.left != null) queue.add(next.left);
            if (next.right != null) queue.add(next.right);
          }
        }
      }
    }
    

  • 0
    J

    very good, I also want to use sequence traversal the tree, and find the very line max number.

    but I use two queues to do this. So result is out of memory.


  • 1
    S

    dude,we almost have the exactly same code in these most recent problems.....


  • 0
    R

    Same to me ^ ^


Log in to reply
 

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