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.
Solution:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int maxD = -1;
int minH = 0;
int val = -1;
public int findBottomLeftValue(TreeNode root) {
pre(root, 0, 0);
return val;
}
private void pre(TreeNode root, int d, int h) {
if (root == null) return;
if (d > maxD || d == maxD && h < minH) {
maxD = d;
minH = h;
val = root.val;
}
pre(root.left, d + 1, h - 1);
pre(root.right, d + 1, h + 1);
}
}