This problem deserves a label "divide and conquer"


  • 0
    N

    The key is to find out which node on the second last layer that doesn't have neither left nor right sub tree. if such node doesn't exist, the tree is a complete binary tree.

    By dividing the tree into left sub tree and right sub tree, you need to find which sub tree contains such node. For the other sub tree that doesn't have this node, it is a complete binary search tree already so you can calculate the number of nodes by its height.

    This way, the original problem is reduced to only half of the original tree. When you go into one sub tree, you are basically solving the same problem on a smaller scale. You can either use recursion or loop that passes down a variable to track the number of nodes you've counted so far.

    Divide and conquer is not a common strategy for tree problems in general because most tree/binary tree are not complete; so you can't really trim off half of it and just focus on one sub tree. this problem is unique in that it tells you it is a complete binary tree already.

    I feel it might be more clear by looking at this problem as divide and conquer. Other people already posted very good solutions so i am not posting mine. Just want to give a little bit insight. Hopefully it's helpful.


Log in to reply
 

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