515. Find Largest Value in Each Tree Row

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]

Solution1:DFS

深度优先,建立一个result linked数组,index(level)上存的就是当前index(level) 行的Max值,linked数组随着level扩大
Time Complexity: O(N) Space Complexity: O(n) worst缓存

Solution2:BFS

广度优先,queue实现,queue中每一组就是一个level中的元素,找出最大依行存下
Time Complexity: O(N) Space Complexity: O(n) worst缓存

Solution1 Code:

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        dfs(root, result, 0);
        return result;
    }
    private void dfs(TreeNode node, List<Integer> result, int level) {
        if(node == null) {
            return;
        }
        
        if(level == result.size()) {
            // expand result list to next level
            result.add(node.val);
        } 
        else { 
            // update max
            result.set(level, Math.max(result.get(level), node.val));
        }
        dfs(node.left, result, level + 1);
        dfs(node.right, result, level + 1);
    }
}

Solution2 Code:

class Solution {
    //BFS 最要在Node进入queue前就进行非空判断,使得进入queue的node本身都非null
    public List<Integer> largestValues(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<Integer> result = new LinkedList<Integer>();
        
        if(root == null) return result;
        
        queue.offer(root);
        while(!queue.isEmpty()) {
            int largest_elem = Integer.MIN_VALUE;
            int num_on_level = queue.size();
            for(int i = 0; i < num_on_level; i++) {
                TreeNode cur = queue.poll();
                largest_elem = Math.max(largest_elem, cur.val);
                if(cur.left != null) queue.add(cur.left);
                if(cur.right != null) queue.add(cur.right);
            }
            result.add(largest_elem);
        }
        
        return result;
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容