?

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]

?

這道題讓我們找二叉樹每行的最大的結(jié)點值，那么實際上最直接的方法就是用層序遍歷，然后在每一層中找到最大值，加入結(jié)果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;} };

?

如果我們想用迭代的方法來解，可以用先序遍歷，這樣的話就需要維護(hù)一個深度變量depth，來記錄當(dāng)前結(jié)點的深度，如果當(dāng)前深度大于結(jié)果res的長度，說明這個新一層，我們將當(dāng)前結(jié)點值加入結(jié)果res中，如果不大于res的長度的話，我們用當(dāng)前結(jié)點值和結(jié)果res中對應(yīng)深度的那個結(jié)點值相比較，取較大值賦給結(jié)果res中的對應(yīng)深度位置，參見代碼如下：

?

解法二：

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 題目講解匯總(持續(xù)更新中...)

總結(jié)

以上是生活随笔為你收集整理的[LeetCode] Find Largest Value in Each Tree Row 找树每行最大的结点值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。