[515. find the maximum value in each tree row]

Given the root node of a binary tree root , Please find the maximum value of each layer in the binary tree .
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]

Tips ：

• The range of the number of nodes in a binary tree is [0,10⁴]
• -2³¹ <= Node.val <= 2³¹ - 1

Method 1 ： Depth-first search

Ideas and algorithms

We use trees 「 The first sequence traversal 」 To carry out 「 Depth-first search 」 Handle , And use \textit{curHeight}curHeight To mark the height of the current node traversed . When traversal to \textit{curHeight}curHeight The height node determines whether to update the maximum value of the layer node .

Code :

class Solution {
    
public:
    void dfs(vector<int>& res, TreeNode* root, int curHeight) {
    
        if (curHeight == res.size()) {
    
            res.push_back(root->val);
        } else {
    
            res[curHeight] = max(res[curHeight], root->val);
        }
        if (root->left) {
    
            dfs(res, root->left, curHeight + 1);
        }
        if (root->right) {
    
            dfs(res, root->right, curHeight + 1);
        }
    }

    vector<int> largestValues(TreeNode* root) {
    
        if (!root) {
    
            return {
    };
        }
        vector<int> res;
        dfs(res, root, 0);
        return res;
    }
};

Execution time ：8 ms, In all C++ Defeated in submission 80.00% Users of
Memory consumption ：21.4 MB, In all C++ Defeated in submission 94.52% Users of
Complexity analysis
Time complexity ： O(n), among n Is the number of binary tree nodes . In the traversal of binary tree, each node will be visited once and only once .
Spatial complexity ： O(height). among height Represents the height of the binary tree . Recursive functions require stack space , And stack space depends on the depth of recursion , So the space complexity is equivalent to the height of the binary tree .

Method 2 ： Breadth first search

Ideas and algorithms

We can also use 「 Breadth first search 」 To solve this problem .「 Breadth first search 」 In the queue, there are 「 All nodes of the current layer 」. Every time you expand to the next level , differ 「 Breadth first search 」 Only one node is taken from the queue at a time , We take out all the nodes in the current queue for expansion , This ensures that all nodes of the next layer are stored in the queue after each expansion , That is, we expand layer by layer , Then on each floor we use maxVal To mark the maximum value of this layer node . When all nodes of this layer are processed , maxVal Is the maximum value of all nodes in this layer .

Code :

class Solution {
    
public:
    vector<int> largestValues(TreeNode* root) {
    
        if (!root) {
    
            return {
    };
        }
        vector<int> res;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
    
            int len = q.size();
            int maxVal = INT_MIN;
            while (len > 0) {
    
                len--;
                auto t = q.front();
                q.pop();
                maxVal = max(maxVal, t->val);
                if (t->left) {
    
                    q.push(t->left);
                }
                if (t->right) {
    
                    q.push(t->right);
                }
            }
            res.push_back(maxVal);
        }
        return res;
    }
};

Execution time ：8 ms, In all C++ Defeated in submission 80.00% Users of
Memory consumption ：21.5 MB, In all C++ Defeated in submission 88.01% Users of
Complexity analysis
Time complexity ： O(n), among n Is the number of binary tree nodes , Each node will enter and leave the queue only once .
Spatial complexity ： O(n), The space cost of storing binary tree nodes .
author： LeetCode-Solution