【515. 在每个树行中找最大值】

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
示例1：

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]

示例2：

输入: root = [1,2,3]
输出: [1,3]

提示：

• 二叉树的节点个数的范围是 [0,10⁴]
• -2³¹ <= Node.val <= 2³¹ - 1

方法一：深度优先搜索

思路与算法

我们用树的「先序遍历」来进行「深度优先搜索」处理，并用 \textit{curHeight}curHeight 来标记遍历到的当前节点的高度。当遍历到 \textit{curHeight}curHeight 高度的节点就判断是否更新该层节点的最大值。

代码:

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;
    }
};

执行用时：8 ms, 在所有 C++ 提交中击败了80.00%的用户
内存消耗：21.4 MB, 在所有 C++ 提交中击败了94.52%的用户
复杂度分析
时间复杂度： O(n)，其中 n 为二叉树节点个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。
空间复杂度： O(height)。其中 height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。

方法二：广度优先搜索

思路与算法

我们也可以用「广度优先搜索」的方法来解决这道题目。「广度优先搜索」中的队列里存放的是「当前层的所有节点」。每次拓展下一层的时候，不同于「广度优先搜索」的每次只从队列里拿出一个节点，我们把当前队列中的全部节点拿出来进行拓展，这样能保证每次拓展完的时候队列里存放的是下一层的所有节点，即我们是一层一层地进行拓展，然后每一层我们用 maxVal 来标记该层节点的最大值。当该层全部节点都处理完后， maxVal 就是该层全部节点中的最大值。

代码:

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;
    }
};

执行用时：8 ms, 在所有 C++ 提交中击败了80.00%的用户
内存消耗：21.5 MB, 在所有 C++ 提交中击败了88.01%的用户
复杂度分析
时间复杂度： O(n)，其中 n 为二叉树节点个数，每一个节点仅会进出队列一次。
空间复杂度： O(n)，存储二叉树节点的空间开销。
author： LeetCode-Solution