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<>();
            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);
            int[] result = new int[res.size()];
            for (int i = 0; i < res.size(); i++) {
                result[i] = res.get(i);
            return result;

  • 0

    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) {
            if (!queue.isEmpty())
          } else {
            if (next.left != null) queue.add(next.left);
            if (next.right != null) queue.add(next.right);

  • 0

    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

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

  • 0

    Same to me ^ ^

Log in to reply

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