7-line JavaScript solution using pre-order DFS


  • 0
    var averageOfLevels = function(root, level = 0, counts = []) {
        if (!root) return;
        counts[level] = counts[level] || { sum: 0, nodes: 0 };
        counts[level].sum += root.val;
        counts[level].nodes++;
        averageOfLevels(root.left, level + 1, counts);
        averageOfLevels(root.right, level + 1, counts);
        return level || counts.map(count => count.sum / count.nodes);
    };
    

  • 0
    X

    @loctn
    First thing that popped into my head is using BFS. And it is easy to implement. Read your code cause I am curious about how to do it with DFS.
    There is one line I don't quite understand. Line 3:

    counts[level] = counts[level] || { sum: 0, nodes: 0 };

    What does it do when you have an "or" operation on two objects?


  • 0
    H

    What do you guys think?

    For good readability of code, a 3*log(n) program and a not good readability O(logn) program, which is better?


  • 0

    Hey @xiangyu6, the || allows us to set the initial object if it doesn't yet exist. The same effect can be achieved with:

    if (!counts[level]) counts.push({ sum: 0, nodes: 0 });
    

    To answer your question, when we || between two objects the first one is taken since objects are truthy.


  • 0

    @Helleoweld I would take the first situation since log n is pretty tiny most of the time, but as usual it depends on use case :).


  • 0

    @Helleoweld Depends on whether the "O(logn) program" is actually better than O(logn). If it isn't, then the complexities are the same and thus the better readability of course determines the winner.

    Btw, why did you ask that here? Doesn't seem to have anything to do with this solution.


  • 0
    H

    It is rare to see javascript topics in this platform! So I ask here!


  • 0

    @Helleoweld to be clear this particular problem is O(n) in time and space, not O(log n), since we indeed need to hit every node to compute averages.

    I also wish there were more JavaScripters interested in algorithms. JS/web interviews tend to be on the practical side unless you are interviewing at Google et al.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.