513. Find Bottom Left Tree Value

Given the root of a binary tree, return the leftmost value in the last row of the tree.

 

Example 1:

Input: root = [2,1,3]
Output: 1

Example 2:

Input: root = [1,2,3,4,null,5,6,null,null,7]
Output: 7

 

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -231 <= Node.val <= 231 - 1

Rust Solution

struct Solution;
use rustgym_util::*;

trait Preorder {
    fn preorder(&self, height: usize, leftmost: &mut (usize, i32));
}

impl Preorder for TreeLink {
    fn preorder(&self, height: usize, leftmost: &mut (usize, i32)) {
        if let Some(node) = self {
            let node = node.borrow();
            let val = node.val;
            let left = &node.left;
            let right = &node.right;
            if height > leftmost.0 {
                *leftmost = (height, val);
            }
            left.preorder(height + 1, leftmost);
            right.preorder(height + 1, leftmost);
        }
    }
}

impl Solution {
    fn find_bottom_left_value(root: TreeLink) -> i32 {
        let mut leftmost: (usize, i32) = (0, 0);
        root.preorder(1, &mut leftmost);
        leftmost.1
    }
}

#[test]
fn test() {
    let root = tree!(2, tree!(1), tree!(3));
    let res = 1;
    assert_eq!(Solution::find_bottom_left_value(root), res);
    let root = tree!(
        1,
        tree!(2, tree!(4), None),
        tree!(3, tree!(5, tree!(7), None), tree!(6))
    );
    let res = 7;
    assert_eq!(Solution::find_bottom_left_value(root), res);
}