Populating Next Right Pointers in Each Node

题目描述

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

You may only use constant extra space. You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children). For example, Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

解题方法

BFS

完全二叉树，所以只需要将level order/right side view的code稍做改动，最右边的next指向None, 其他的都指向queue里面的下一个

空间O(1)

两个节点node负责换层(node=node->left), cross负责把左右子树连起来，以及右子树和corss->next的左子树连起来。

Solution

from collections import deque
# Definition for binary tree with next pointer.
# class TreeLinkNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None

class Solution(object):
    def connect(self, root):
        """
        :type root: TreeLinkNode
        :rtype: nothing
        """
        if not root:
            return
        queue = deque()
        result = []
        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)

space O(1)

• 用node变量来遍历每一层，node一直是每层的最左边的node
• 然后在每一层都将下一层的next连接起来，用一个cross一直往右来连接

class Solution(object):
    def connect(self, root):
        """
        :type root: TreeLinkNode
        :rtype: nothing
        """
        if not root:
            return
        node = root
        while node:
            cross = node
            while cross:
                if cross.left:
                    cross.left.next = cross.right
                if cross.right and cross.next:
                    cross.right.next = cross.next.left
                cross = cross.next
            node = node.left

Reference