42 lines
1 KiB
C++
42 lines
1 KiB
C++
#include <cassert>
|
|
#include <map>
|
|
#include <optional>
|
|
|
|
#ifdef _MF_TEST
|
|
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) {}
|
|
};
|
|
#endif
|
|
|
|
class Solution {
|
|
void find_bottom_left(std::map<int, std::optional<int>> &view, int y,
|
|
TreeNode *node) {
|
|
if (node == nullptr) {
|
|
return;
|
|
}
|
|
|
|
auto &leftmost = view[y];
|
|
if (!leftmost.has_value()) {
|
|
leftmost = std::make_optional(node->val);
|
|
}
|
|
|
|
find_bottom_left(view, y - 1, node->left);
|
|
find_bottom_left(view, y - 1, node->right);
|
|
}
|
|
|
|
public:
|
|
int findBottomLeftValue(TreeNode *root) {
|
|
assert(root != nullptr);
|
|
|
|
std::map<int, std::optional<int>> leftview;
|
|
|
|
find_bottom_left(leftview, 0, root);
|
|
return leftview.begin()->second.value();
|
|
}
|
|
};
|