题目大意：给你一棵树，返回每一层最大的元素的值。
You need to find the largest value in each row of a binary tree.
Example:
|
1 2 3 4 5 6 7 8 9 |
<b>Input:</b> 1 / \ 3 2 / \ \ 5 3 9 <b>Output:</b> [1, 3, 9] |
Solution 1: Inorder traversal + depth info
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua // Running time: 15 ms class Solution { public: vector<int> largestValues(TreeNode* root) { vector<int> ans; inorder(root, 0, ans); return ans; } private: void inorder(TreeNode* root, int d, vector<int>& ans) { if (root == nullptr) return; while (ans.size() <= d) ans.push_back(INT_MIN); inorder(root->left, d + 1, ans); ans[d] = max(ans[d], root->val); inorder(root->right, d + 1, ans); } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
""" Author: Huahua Running time: 72 ms (beats 100%) """ class Solution: def largestValues(self, root): def inorder(root, d, ans): if not root: return ans if len(ans) <= d: ans += [float('-inf')] inorder(root.left, d + 1, ans) if root.val > ans[d]: ans[d] = root.val inorder(root.right, d + 1, ans) return ans return inorder(root, 0, []) |