首页 > itarticle > 算法笔记: 力扣#637 二叉树的层平均值

算法笔记: 力扣#637 二叉树的层平均值

admin 11月 12, 2020 0

问题描述

解法

分析

Python 实现

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class :
    def averageOfLevels(self, root):
        """
        :type root: TreeNode
        :rtype: List[float]
        """
        res = []
        cnt = []
        
        def getLevelSum(node, level):
            if len(res) <= level:
                res.append(node.val)
                cnt.append(1)
            else:
                res[level] += node.val
                cnt[level] += 1
            if node.left:
                getLevelSum(node.left, level+1)
            if node.right:
                getLevelSum(node.right, level+1)
                
        getLevelSum(root, 0)
        return [s/c for s, c in zip(res, cnt)]

Java 实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class  {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        List<Integer> cnt = new ArrayList<>();
        getLevelSum(root, 0, res, cnt);
        
        for(int i = 0; i < res.size(); i++){
            res.set(i, res.get(i)/cnt.get(i));
        }
        
        return res;
    }
    
    private void getLevelSum(TreeNode node, int level, List<Double> res, List<Integer> cnt){
        if(node == null){ return; }
        if(res.size() <= level){
            res.add(node.val * 1.0);
            cnt.add(1);
        }else{
            res.set(level, res.get(level) + node.val);
            cnt.set(level, cnt.get(level) + 1);
        }
        getLevelSum(node.left, level+1, res, cnt);
        getLevelSum(node.right, level+1, res, cnt);
    }
}

时间复杂度

O(N).

空间复杂度

O(L).

链接

637. Average of Levels in Binary Tree
637. 二叉树的层平均值
 (English version) Algorithm Notes: Leetcode#637 Average of Levels in Binary Tree