Java
import java.util.LinkedList;
import java.util.Queue;
/**
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.
*/
public class Find_Bottom_Left_Tree_Value {
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int findBottomLeftValue(TreeNode root) {
// bfs
if (root == null) {
return -1;
}
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int currentLevelCount = 1;
int nextLevelCount = 0;
int result = root.val;
boolean isLevelLeftMost = false;
while (!q.isEmpty()) {
TreeNode current = q.poll();
currentLevelCount--;
// check leftmost
if (isLevelLeftMost) {
result = current.val;
isLevelLeftMost = false;
}
if (current.left != null) {
q.offer(current.left);
nextLevelCount++;
}
if (current.right != null) {
q.offer(current.right);
nextLevelCount++;
}
if (currentLevelCount == 0) {
currentLevelCount = nextLevelCount;
nextLevelCount = 0;
// mark next node of queue is the possible result
isLevelLeftMost = true;
}
}
return result;
}
}
}Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int findBottomLeftValue(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int bottomLeftValue = 0;
while (!queue.isEmpty()) {
int size = queue.size();
bottomLeftValue = queue.peek().val;
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
TreeNode left = node.left, right = node.right;
if (left != null)
queue.offer(left);
if (right != null)
queue.offer(right);
}
}
return bottomLeftValue;
}
}