【剑斩OFFER】算法的暴力美学——leetCode 515 题：在每个树行中找到最大值

一、题目描述

二、算法原理

思路：层序遍历每一层的最大值

三、代码实现

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> largestValues(TreeNode* root) { if(root == nullptr) return {}; queue<TreeNode*> que; que.push(root); vector<int> ret; while(que.size()) { int maxi = INT_MIN; int size = que.size();//层序遍历 while(size--) { TreeNode* node = que.front(); maxi = max(node->val,maxi);//比较当前层的最大值 que.pop(); if(node->left != nullptr) que.push(node->left); if(node->right != nullptr) que.push(node->right); } ret.push_back(maxi); } return ret; } };