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

results matching ""

    No results matching ""