515. Find Largest Value in Each Tree Row

515. Find Largest Value in Each Tree Row (Medium)

Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

 

Example 1:

Input: root = [1,3,2,5,3,null,9]
Output: [1,3,9]

Example 2:

Input: root = [1,2,3]
Output: [1,3]

 

Constraints:

• The number of nodes in the tree will be in the range [0, 104].
• -231 <= Node.val <= 231 - 1

Companies:
Facebook, Samsung

Related Topics:
Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution 1. BFS

// OJ: https://leetcode.com/problems/find-largest-value-in-each-tree-row/
// Author: github.com/lzl124631x
// 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;
    }
};

Solution 2. DFS

// OJ: https://leetcode.com/problems/find-largest-value-in-each-tree-row/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(logN)
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        if (!root) return {};
        vector<int> ans;
        function<void(TreeNode*, int)> dfs = [&](TreeNode *root, int d) {
            if (!root) return;
            if (d == ans.size()) ans.push_back(INT_MIN);
            ans[d] = max(ans[d], root->val);
            dfs(root->left, d + 1);
            dfs(root->right, d + 1);
        };
        dfs(root, 0);
        return ans;
    }
};