Java

  • import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    
    /**
    
     You need to find the largest value in each row of a binary tree.
    
     Example:
     Input:
    
        1
       / \
      3   2
     / \   \
    5   3   9
    
     Output: [1, 3, 9]
    
     */
    
    public class Find_Largest_Value_in_Each_Tree_Row {
    
        /**
         * Definition for a binary tree node.
         * public class TreeNode {
         *     int val;
         *     TreeNode left;
         *     TreeNode right;
         *     TreeNode(int x) { val = x; }
         * }
         */
        class Solution {
            public List<Integer> largestValues(TreeNode root) {
    
                List<Integer> result = new ArrayList<>();
    
                // bfs
                if (root == null) {
                    return result;
                }
    
                Queue<TreeNode> q = new LinkedList<>();
                q.offer(root);
                int currentLevelCount = 1;
                int nextLevelCount = 0;
    
                int currentLevelMax = root.val;
    
                while (!q.isEmpty()) {
                    TreeNode current = q.poll();
                    currentLevelCount--;
    
                    // check leftmost
                    currentLevelMax = Math.max(currentLevelMax, current.val);
    
                    if (current.left != null) {
                        q.offer(current.left);
                        nextLevelCount++;
                    }
                    if (current.right != null) {
                        q.offer(current.right);
                        nextLevelCount++;
                    }
    
                    if (currentLevelCount == 0) {
                        currentLevelCount = nextLevelCount;
                        nextLevelCount = 0;
    
                        result.add(currentLevelMax);
    
                        // reset
                        currentLevelMax = Integer.MIN_VALUE;
                    }
                }
    
                return result;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/find-largest-value-in-each-tree-row/
    // Time: O(N)
    // Space: O(N)
    class Solution {
    public:
        vector<int> largestValues(TreeNode* root) {
            if (!root) return {};
            vector<int> ans;
            queue<TreeNode*> q{ {root} };
            while (q.size()) {
                int cnt = q.size(), maxVal = INT_MIN;
                while (cnt--) {
                    auto n = q.front();
                    q.pop();
                    maxVal = max(maxVal, n->val);
                    if (n->left) q.push(n->left);
                    if (n->right) q.push(n->right);
                }
                ans.push_back(maxVal);
            }
            return ans;
        }
    };
    
  • # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
      def largestValues(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        ans = []
        d = {}
    
        def dfs(root, h, d):
          if root:
            dfs(root.left, h + 1, d)
            dfs(root.right, h + 1, d)
            d[h] = max(d.get(h, float("-inf")), root.val)
    
        dfs(root, 0, d)
        level = 0
        while level in d:
          ans += d[level],
          level += 1
        return ans
    
    

All Problems

All Solutions