513. Find Bottom Left Tree Value

Version #1 BFS

一刷
妈呀这题简直神了
直接从右向左BFS
返回最后一个值就行了
37.01 %
public class Solution {
    public int findBottomLeftValue(TreeNode root) {
        if (root == null) throw new IllegalArgumentException();
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        TreeNode curr = root;
        while (!que.isEmpty()) {
            curr = que.poll();
            if (curr.right != null) que.offer(curr.right);
            if (curr.left != null) que.offer(curr.left);
        }
        return curr.val;
    }
}

Version #2 DFS

一刷
99.87 %
class Solution {
    private int deepest = -1;
    private int value;
    public int findBottomLeftValue(TreeNode root) {
        helper(root, 0);
        return value;
    }
    private void helper(TreeNode node, int depth) {
        if (depth > deepest) {
            deepest = depth;
            value = node.val;
        }
        if (node.left != null) {
            helper(node.left, depth + 1);
        }
        if (node.right != null) {
            helper(node.right, depth + 1);
        }
    }
}

二刷

Time O(n), n->number of tree nodes

Runtime: 0 ms, faster than 100.00% of Java online submissions for Find Bottom Left Tree Value.

Memory Usage: 39 MB, less than 22.87% of Java online submissions for Find Bottom Left Tree Value.

class Solution {

    private int maxDepth = Integer.MIN_VALUE;

    private int resNodeVal;

    public int findBottomLeftValue(TreeNode root) {

        // find the first node with max depth

        dfs(root, 0);

        return resNodeVal;

        

    }

    // dfs: each node add one to depth and pass it to it's children

    // update the max depth if possible

    private void dfs(TreeNode node, int depth) {

        if (node == null) {

            return;

        }

        depth++;

        if (depth > maxDepth) {

            maxDepth = depth;

            resNodeVal = node.val;

        }

        dfs(node.left, depth);

        dfs(node.right, depth);

    }

}