FindLargestValueInEachTreeRow [source code]
public class FindLargestValueInEachTreeRow {
static
/******************************************************************************/
public class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null)
return res;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
int max = Integer.MIN_VALUE;
for (int i = 0; i < size; i++) {
TreeNode t = q.poll();
if (t.val > max)
max = t.val;
if (t.left != null)
q.offer(t.left);
if (t.right != null)
q.offer(t.right);
}
res.add(max);
}
return res;
}
}
/******************************************************************************/
public static void main(String[] args) {
FindLargestValueInEachTreeRow.Solution tester = new FindLargestValueInEachTreeRow.Solution();
}
}
很简单的一个题目, 速度是11(49). 速度有点平庸, 不知道为什么;
刚开始里面的循环的i的起点写成了1, 结果死循环,死活改不出来, 只能说真的蠢;
这个题目的标准做法肯定是BFS. 这个是discussion里面一个用DFS来做的:
public class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
helper(root, res, 0);
return res;
}
private void helper(TreeNode root, List<Integer> res, int d){
if(root == null){
return;
}
//expand list size
if(d == res.size()){
res.add(root.val);
}
else{
//or set value
res.set(d, Math.max(res.get(d), root.val));
}
helper(root.left, res, d+1);
helper(root.right, res, d+1);
}
}
核心思路就是: 用depth tag在DFS当中来帮助寻找level start. 因为level的start(最左边端点)肯定是DFS的过程中(如果你的order正常些的话)第一个在该level当中被visit的是, 所以这个时候res list的size肯定还比depth小1; 而level后面的node, 因为这个时候level左端点已经导致当前level对应的max被初始化了, 所以这个时候的res的size跟这个node的depth肯定就相等的;
按理说这个算法因为要多次的access linked list by index, 我认为可能速度不怎么样, 但是实际上速度是10ms, 估计DFS这种依赖recursion的算法最后还是享受了很多自带的优化的;
注意这里要用PreOrder; 这样在左边大梁的时候才能保证下面的node进入的时候, 所有上面的level都已经被初始化;
在BFS当中你维护的这个queue的size是有可能达到N/2
的, 而在DFS当中, Stack的size最多只可能到lgN
.
其他的, 基本discussion也没有什么特别的思路了;
submission也没有什么惊喜, DFS的最快, 速度基本是10, BFS的是11;
Problem Description
You need to find the largest value in each row of a binary tree.
Example:
Input:
1
/ \
3 2
/ \ \
5 3 9
Output: [1, 3, 9]
Difficulty:Medium
Total Accepted:19.2K
Total Submissions:35.1K
Contributor: CDY_好きだ
Companies
linkedin
Related Topics
tree depth-first search breadth-first search