FindBottomLeftTreeValue [source code]

public class FindBottomLeftTreeValue {
static
/******************************************************************************/
public class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int[] maxes = new int[2];
        dfs(root, maxes, 1);
        return maxes[1];
    }

    public void dfs(TreeNode root, int[] maxes, int depth) {
        if (root == null) return;
        dfs(root.left, maxes, depth + 1);
        dfs(root.right, maxes, depth + 1);
        if (depth > maxes[0]) {
            maxes[0] = depth;
            maxes[1] = root.val;
        }
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        FindBottomLeftTreeValue.Solution tester = new FindBottomLeftTreeValue.Solution();
    }
}

这个题目总体感觉不算难的, 用DFS或者BFS其实都能做; 用BFS做的话, 每一个level维护第一个出现的val就行了; 用DFS, 就要tag一个depth(不是height);

感觉DFS难一点, 所以用DFS写写看; 这一题的DFS感觉什么order都可以, 反正就是跑一个max; 不过为了减少accum被更新的次数, 我认为PostOrder好一些(这样最大的depth就先被放到accum里面, 较小的accum就没有机会更新了);

这个题目整体来说还是比较简单的;

一个小的问题, 你给大root的depth应该是多少? 因为我们这里没有对accum进行初始化(比如到MIN_VALUE), 所以我们这里要保证每一个node的depth都要大于0(the default value for accum). 所以给大root的depth一定要大于0;

最后的速度是8ms (69%), 可以接受;

discussion的BFS:

public class Solution {  
    public int findLeftMostNode(TreeNode root) {  
        if (root == null) return 0;  

        int result = 0;  
        Queue<TreeNode> queue = new LinkedList<>();  
        queue.add(root);  

        while (!queue.isEmpty()) {  
            int size = queue.size();  
            for (int i = 0; i < size; i++) {  
                TreeNode node = queue.poll();  
                if (i == 0) result = node.val;  
                if (node.left != null) queue.add(node.left);  
                if (node.right != null) queue.add(node.right);  
            }  
        }  

        return result;  
    }  
}

可以看到, 就是用res来维护每一个level的第一个poll出来的值, 很简单的一个思路;

这个是stefan在discussion上的一个很有意思的解法:

Doing BFS right-to-left means we can simply return the last node's value and don't have to keep track of the first node in the current row or even care about rows at all. Inspired by @fallcreek's solution (not published) which uses two nested loops to go row by row but already had the right-to-left idea making it easier. I just took that further.

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;  
}

这个想法确实是很奇葩的, 而且也让我再次见识到了一次variation of BFS in action;

--
这题最后submission的最优解居然是PreOrder, 这个我还真是没有想到; 不知道为什么, 速度是6ms;

Problem Description

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.

Difficulty:Medium
Total Accepted:21.4K
Total Submissions:38.6K
Contributor: abhijeet17
Companies
microsoft
Related Topics
tree depth-first search breadth-first search