Level Order

题目列表

• level-order
• level-order 2
• zigzag
• populate next right pointers I & II

解题方法

Level order

1. 用变量记录当前层和下一层的node数量
2. 不用变量记录，每次记录当前queue的size，就是这一层的数量，然后从queue中 pop出相应数量的node，并且将它们的child加到queue中

populate next right pointers

1. complete tree

2. not complete

3. level order的做法还是可以做的

4. constant space的做法，每次用上一层的来处理下一层的next问题

利用queue

class Solution(object):
    def connect(self, root):
        """
        :type root: TreeLinkNode
        :rtype: nothing
        """
        if not root:
            return
        queue = deque()
        queue.append(root)
        while queue:
            size = len(queue)
            for i in range(size):
                cur = queue.popleft()
                if i == size - 1:
                    cur.next = None
                else:
                    cur.next = queue[0]
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)

O(1) space的做法

1. 上一层的开头和指针，当前层的开头和指针
2. 每次用上一层的指针移动，当前层的指针随之移动
3. 在移动的过程中如果curHead还是None，说明还没有到下一层的开头

class Solution(object):
    def connect(self, root):
        """
        :type root: TreeLinkNode
        :rtype: nothing
        """
        if not root:
            return
        lastHead = root
        lastCurrent = None
        curHead = None
        cur = None

        while lastHead:
            lastCurrent = lastHead
            while lastCurrent:
                if lastCurrent.left:
                    if curHead is None:
                        curHead = lastCurrent.left
                        cur = curHead
                    else:
                        cur.next = lastCurrent.left
                        cur = cur.next
                if lastCurrent.right:
                    if curHead is None:
                        curHead = lastCurrent.right
                        cur = curHead
                    else:
                        cur.next = lastCurrent.right
                        cur = cur.next
                lastCurrent = lastCurrent.next
            lastHead = curHead
            curHead = None

Solution

Reference