513 Find Bottom Left Tree Value
Given a binary tree, find the leftmost value in the last row of the tree.
Example 1:
Input:
2
/ \
1 3
Output:
1
Example 2:
Input:
1
/ \
2 3
/ / \
4 5 6
/
7
Output:
7
Note:You may assume the tree (i.e., the given root node) is not NULL.
Complexity: O(n) time, O(logn) space
The Idea: Run a level order traversal with a small twist: check for instances when the next level arises (left to right top to bottom), and collect the first left instance.
int findBottomLeftValue(TreeNode* root) {
if (!root) return -1;
int deepest_left = root->val;
queue<TreeNode*> q;
q.push(root);
q.push(nullptr);
while (!q.empty()) {
TreeNode *temp = q.front();
q.pop();
if (temp) {
if (temp->left)
q.push(temp->left);
if (temp->right)
q.push(temp->right);
}
else {
if (!q.empty() && q.front()) {
deepest_left = q.front()->val;
q.push(nullptr);
}
}
}
return deepest_left;
}
Last modified 4yr ago