This is what I have drawn

I am apparently missing something. How to include the value at index 10 of the array? I will be grateful for your help.

CodePudding user response：

The array encoding is not such that you can assume that a node's children are at the index i*2 1 and i*2 2. That would be true if the encoded tree were a complete binary tree, but when it is not, you cannot use this formula.

Instead, you should keep track of the bottom layer of the tree as you build it, only registering real nodes (not null). Then distribute the next children among the nodes in the (then) bottom layer, etc. This is really a breadth-first traversal method.

This is the procedure:

Create a queue, and create a node for the first value in the input list (if the list is not empty), and enqueue it.

Then repeat for as long as there is more input to process:

• dequeue a node from the queue
• read the next two values from the input, and create nodes for them. If there are not enough values remaining in the input, use null instead.
• Attach these two nodes as children to the node that you had taken from the queue
• Those children that were not null should be enqueued on the queue.

If you apply this algorithm to the example input [1,2,2,3,null,null,3,4,null,null,4], then we get first the root, which is put on the queue. So just before the loop starts we have:

        root: 1        queue = [1]
                       remaining input = [2,2,3,null,null,3,4,null,null,4]

I depict here the queue contents with numbers, but they really are node instances.

After the first iteration of the loop, in which we read 2 and 2 from the input, create nodes for them, attach them to the dequeued node, and enqueue those children, we get:

        root: 1        queue = [2, 2]
             / \       remaining input = [3,null,null,3,4,null,null,4]
            2   2

After iteration #2 (note that no null is enqueued):

        root: 1        queue = [2, 3]
             / \       remaining input = [null,3,4,null,null,4]
            2   2
           / *
          3    

After iteration #3:

        root: 1        queue = [3, 3]
             / \       remaining input = [4,null,null,4]
            2   2
           / * * \
          3       3

After iteration #5:

        root: 1        queue = [3, 4]
             / \       remaining input = [null,4]
            2   2
           / * * \
          3       3
         / *
        4

After the final iteration:

        root: 1        queue = [4, 4]
             / \       remaining input = []
            2   2
           / * * \
          3       3
         / *     * \
        4           4

The queue is not empty, but as there is no more input, those queued nodes represent leaves that need no further processing.