Java O(n) Easy To Understand, Optimal Solution


  • 0
    B

    Explanation
    The idea to this question is to write to a list as we DFS through the tree, using the depth as our index for the list. If a node's value in a level is greater than the existing one within our list, we overwrite it.

    Time Complexity
    The time complexity is O(n) where n is the number of nodes in our tree root, since we traverse through the entire tree.

    class Solution {
        public List<Integer> largestValues(TreeNode root) {
            List<Integer> result = new ArrayList<>();
            largestValuesHelper(root, result, 0);
            return result;
        }
        
        public void largestValuesHelper(TreeNode root,
                                   List<Integer> result, int depth) {
            if (root == null) return;
    
            // List size is not large enough for index depth
            if (result.size() == depth) {
                result.add(root.val);
            } 
            // Check if root.val is greater than existing entry
            else if (root.val > result.get(depth)) {
                result.set(depth, root.val);
            }
            largestValuesHelper(root.left, result, depth + 1);
            largestValuesHelper(root.right, result, depth + 1);
        }
    }
    

Log in to reply
 

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