# LC 515. Find Largest Value in Each Tree Row

### [Problem link](https://leetcode.com/problems/find-largest-value-in-each-tree-row/)

###### tags: `leedcode` `medium` `c++` `Binary Tree`

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

**Example 1:**
<img alt="" src="https://assets.leetcode.com/uploads/2020/08/21/largest_e1.jpg" style="width: 300px; height: 172px;" />

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 <code>[0, 10⁴]</code>.
- <code>-2³¹ <= Node.val <= 2³¹ - 1</code>

## Solution 1
#### C++

// iteration
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> res;
        queue<TreeNode*> q;

        if (root != nullptr) {
            q.push(root);
        }
        while (!q.empty()) {
            int size = q.size();
            int level_max = INT_MIN;

            for (int i = 0; i < size; i++) {
                TreeNode *node = q.front();
                q.pop();

                level_max = max(level_max, node->val);
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
            res.push_back(level_max);
        }
        return res;
    }
};

// recursive
class Solution {
public:
    void traversal(TreeNode *node, vector<vector<int>> &vec, int level) {
        if (node == nullptr) {
            return;
        }
        if (vec.size() == level) {
            vec.push_back(vector<int>());
        }
        vec[level].push_back(node->val);
        traversal(node->left, vec, level + 1);
        traversal(node->right, vec, level + 1);
    }

    vector<int> largestValues(TreeNode* root) {
        vector<vector<int>> record;
        traversal(root, record, 0);

        vector<int> res;
        for (vector<int> &v: record) {
            int level_max = INT_MIN;
            for (int &num: v) {
                level_max = max(level_max, num);
            }
            res.push_back(level_max);
        }
        return res;
    }
};

>### Complexity
>n = number of tree’s nodes
>l = number of tree's level nodes
>| | Time Complexity | Space Complexity |
>| ---------------------- | --------------- | ---------------- |
>| Solution 1(iteration) | O(n) | O(l) |
>| Solution 1(recursive) | O(n) | O(n) |

## Note
x
[](https://)