I am having trouble understanding what is wrong with my code and understanding constraint below.

My pseudocode:

1. Traverse the tree Level Order and construct the array representation (input is actually given as a single root, but they use array representation to show the full tree)
2. iterate over this array representation, skipping null nodes
3. for each node, lets call it X, iterate upwards until we reach the root checking to see if at any point in the path, parentNode > nodeX, meaning, nodeX is not a good node.
4. increment counter if the node is good

Constraints:

• The number of nodes in the binary tree is in the range [1, 10^5].
• Each node's value is between [-10^4, 10^4]

First of all: My confusion on the constraint is that, the automated tests are giving input such as [2,4,4,4,null,1,3,null,null,5,null,null,null,null,5,4,4] and if we follow the rules that childs are at c1 = 2k 1 and c2 = 2k 2 and parent = (k-1)//2 then this means that there are nodes with value null

Secondly: For the input above, my code outputs 8, the expected value is 6, but when I draw the tree from the array, I also think the answer should be 8 !

CodePudding user response：

The binary heap you provided corresponds to the folloring hierarchy:

tree = [2,4,4,4,None,1,3,None,None,5,None,None,None,None,5,4,4]
printHeapTree(tree)

    2
   / \
  4   4
 /   / \
4   1   3
         \
          5

In that tree, only item value 1 has an ancestor that is greater than itself. All 6 other nodes only have ancestors that are <= to themselves (counting the root as good).

Note that the last three values in the list are unreachable because their parent is null (None) so they are not part of the tree (this could be a copy/paste mistake though). Or perhaps the list is not a binary heap and some other processing rules need to be specified.

You can find the printHeapTree() function here.