How to construct a binary tree from Leetcode values list?

Question

For the following problem:

The output/correct result is specified as:

 Output: [3,9,20,null,null,15,7]

I'm not sure what that output actually represents. I tried to scan it by level . E.g 3 is the root, then its children are 9 and 20 (which does not work). So then what is the actual tree?

Elanorelapid

It looks like a BFS - first level is 3, second - 9 and 20, the last - null, null (children of 9), 15 and 7. – Kela

LeetCode normally does this conversion for you. In your solution could you should really return an object-oriented instance of the tree, using the Node class or whatever the comment block before the template code suggests (it depends on the programming language). The LeetCode testing suite will silently convert your structured return value to this array format. It is not something you are supposed to take care of. – Exospore

Answer 1

It's how the binary tree is represented.

Output is a list of nodes where for node i (starting from index 0), node 2*i+1 is its left child and node 2*i+2 is its right child. So if those nodes do not exist, the corresponding value in the list is represented as NULL.

In this case, node 0 has a value of 3, and its left child is shown in node 1 (Output[1]) with value 9, while its right child is shown in node 2 (Output[2]) with value 20.

However, node 2 (Output[2] with value 20) does not have any children so the values corresponding to its children (Output[3], Output[4]) are shown as Null.

Buttonhook

What you mention is how I was reading it but thought that were not correct. So this is not a sorted binary tree? – Elanorelapid

That seems to be what they mean. Binary trees aren't necessarily sorted. – Buttonhook

Answer 2

I think we need a queue to store the parent to be written and we can use the index to determine whether to write the left(odd) child or right(even) child of the parent node. here is a solution written in python3, it returns the root node of the tree. I tested problem 437' input and it worked out, and this can also solve the input you posted. If the code has any problem, please let me know, I would like to help.

def buildTree(nodes: list) -> TreeNode:
    n = len(nodes)

    if n == 0:
        return None
    
    parentStack = collections.deque()
    root = TreeNode(nodes[0])
    curParent = root

    for i in range(1, n):
        if i % 2 == 1:
            if nodes[i] is not None:
                curParent.left = TreeNode(nodes[i])
                parentStack.append(curParent.left)
        else:
            if nodes[i] is not None:
                curParent.right = TreeNode(nodes[i])
                parentStack.append(curParent.right)
            
            curParent = parentStack.popleft()

    return root

Footrace

Answer 3

C# implementation of algo:

TreeNode? BuildTree(List<int?> nodes) {
    int n = nodes.Count;
    if (n == 0) return null;
    Queue<TreeNode> parentQueue = new();
    TreeNode root = new(nodes[0] ?? throw new InvalidOperationException());
    TreeNode curParent = root;
    for (int i = 1; i < n; i++) {
        var node = nodes[i];
        if (i % 2 == 1) {
            if (node != null) {
                curParent.left = new TreeNode(node.Value);
                parentQueue.Enqueue(curParent.left);
            }
        }
        else {
            if (node != null) {
                curParent.right = new TreeNode(node.Value);
                parentQueue.Enqueue(curParent.right);
            }

            curParent = parentQueue.Dequeue();
        }
    }
    return root;
}

Masson