首页 > 代码库 > [LeetCode] Find Largest Value in Each Tree Row 找树每行最大的结点值
[LeetCode] Find Largest Value in Each Tree Row 找树每行最大的结点值
You need to find the largest value in each row of a binary tree.
Example:
Input: 1 / 3 2 / \ \ 5 3 9 Output: [1, 3, 9]
这道题让我们找二叉树每行的最大的结点值，那么实际上最直接的方法就是用层序遍历，然后在每一层中找到最大值，加入结果res中即可，参见代码如下：
解法一：
class Solution {public: vector<int> largestValues(TreeNode* root) { if (!root) return {}; vector<int> res; queue<TreeNode*> q; q.push(root); while (!q.empty()) { int n = q.size(), mx = INT_MIN; for (int i = 0; i < n; ++i) { TreeNode *t = q.front(); q.pop(); mx = max(mx, t->val); if (t->left) q.push(t->left); if (t->right) q.push(t->right); } res.push_back(mx); } return res; }};
如果我们想用迭代的方法来解，可以用先序遍历，这样的话就需要维护一个深度变量depth，来记录当前结点的深度，如果当前深度大于结果res的长度，说明这个新一层，我们将当前结点值加入结果res中，如果不大于res的长度的话，我们用当前结点值和结果res中对应深度的那个结点值相比较，取较大值赋给结果res中的对应深度位置，参见代码如下：
解法二：
class Solution {public: vector<int> largestValues(TreeNode* root) { if (!root) return {}; vector<int> res; helper(root, 1, res); return res; } void helper(TreeNode* root, int depth, vector<int>& res) { if (depth > res.size()) res.push_back(root->val); else res[depth - 1] = max(res[depth - 1], root->val); if (root->left) helper(root->left, depth + 1, res); if (root->right) helper(root->right, depth + 1, res); }};
参考资料：
https://discuss.leetcode.com/topic/79241/simple-and-easy-understand-c-dfs-solution
LeetCode All in One 题目讲解汇总(持续更新中...)
[LeetCode] Find Largest Value in Each Tree Row 找树每行最大的结点值
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。