Thursday, June 23, 2016

link node to its right / left neighbor for every node in binary tree

node:
    left, right
    next

(node):
    if node == null:
        throw
    q = new
    level = 0
    q.enqueue({node, level})
    while !q.empty():
        prevn = null
        while !q.isempty() && q.peek().level == level:
            n, nlevel = q.dequeue()
            // link to right
            if prevn != null:
                prevn.next = n
            prevn = n
            // link to left
            n.next = prevn
            prevn = n
            if n.left != null:
                q.enqueue({n.left, nlevel+1})
            if n.right != null:
                q.enqueue({n.right, nlevel+1})
        level++
[Hat tip to PC]

No comments:

Post a Comment