513. Find Bottom Left Tree Value.md

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.

---

Solution

• mine

//D = depth  O(2^D) time  O(2^D) space
/**
 * 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) {
        List<TreeNode> list = new ArrayList<>();
        list.add(root);
        for(int i = 0; i < list.size(); i++){
            TreeNode temp = list.get(i);
            if(temp.right != null){
                list.add(temp.right);
            }
            if(temp.left != null){
                list.add(temp.left);
            }
        }
        
        return list.get(list.size() - 1).val;
    }
}

• the most votes

//D = depth  O(2^D) time  O(2^D) space
public int findLeftMostNode(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        root = queue.poll();
        if (root.right != null)
            queue.add(root.right);
        if (root.left != null)
            queue.add(root.left);
    }
    return root.val;
}

• other

// D = depth  O(2^D) time  O(1) space
public class Solution {
    public int findBottomLeftValue(TreeNode root) {
        return findBottomLeftValue(root, 1, new int[]{0,0});
    }
    public int findBottomLeftValue(TreeNode root, int depth, int[] res) {
        if (res[1]<depth) {res[0]=root.val;res[1]=depth;}
        if (root.left!=null) findBottomLeftValue(root.left, depth+1, res);
        if (root.right!=null) findBottomLeftValue(root.right, depth+1, res);
        return res[0];
    }
}