513. Find Bottom Left Tree Value

Description

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

Example 1:

Input:

tree

Output:
1

Example 2:

Input:

tree

Output:
7

Note: You may assume the tree (i.e., the given root node) is not NULL.

Solution

DFS

/**
 * 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) {
        return dfs(root)[1];
    }
    // return int[] {height, leftMostValueInLastRow}
    public int[] dfs(TreeNode root) {
        if (root == null) {
            return new int[] {0, Integer.MIN_VALUE};
        }
        
        if (root.left == null && root.right == null) {
            return new int[] {1, root.val};
        }
        
        int[] left = dfs(root.left);
        int[] right = dfs(root.right);
        if (left[0] >= right[0]) {
            ++left[0];
            return left;
        } else {
            ++right[0];
            return right;
        }
    }
}

BFS

层序遍历，val更新为每层第一个节点的val。

/**
 * 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) {
        int val = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);  // root is non-null;
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            
            for (int i = 0; i < size; ++i) {
                TreeNode curr = queue.poll();
                if (i == 0) {
                    val = curr.val;
                }
                
                if (curr.left != null) {
                    queue.offer(curr.left);
                }
                
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
            }
        }
        
        return val;
    }
}

Right-to-Left BFS

很妙啊，从右到左层序遍历就可以保证最后一个访问到的元素即为所求。

/**
 * 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) {
        int val = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);  // root is non-null;
        
        while (!queue.isEmpty()) {
            TreeNode curr = queue.poll();
            val = curr.val;
            
            if (curr.right != null) {
                queue.offer(curr.right);
            }
            if (curr.left != null) {
                queue.offer(curr.left);
            }
        }
        
        return val;
    }
}