leetcode_深度搜索和广度搜索 116. 填充每个节点的下一个右侧节点指针

116. 填充每个节点的下一个右侧节点指针

• 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。
• 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
• 初始状态下，所有 next 指针都被设置为 NULL。
• 思路:

  • 对于完美二叉树，可以利用每一层的节点之间的连接关系：其左子节点的 next 应该指向右子节点，右子节点的 next 指向它的兄弟节点的 next（如果有的话）。由于每个节点都有两个子节点，并且二叉树是完美的（即所有叶子节点都在同一层），得出以下步骤：

    1. 从树的根节点开始，逐层处理。由于根节点的本身没有右侧节点，且next初始值为none，故不用单独处理
    2. 遍历当前层数的每一个节点
    3. 对于每一个节点，如果它有左子节点，则把左子节点的 next 指针指向右子节点（level_node.left.next = level_node.right）；如果它有右子节点，则把右子节点的 next 指针指向当前节点的 next 的左子节点（level_node.right.next = level_node.next.left）
    4. 在完成当前层的连接后，进入下一层（cur = cur.left）

# Definition for a Node.
class Node(object):
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

"""

class Solution(object):
    def connect(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        if not root:
            return None
        
        # 从根节点开始处理
        cur = root
        
        # 每一层的遍历
        while cur:
            # 遍历当前层的每个节点
            level_node = cur
            while level_node:
                # 连接左子节点和右子节点
                if level_node.left:
                    level_node.left.next = level_node.right
                
                # 连接右子节点和当前节点的下一个节点的左子节点
                if level_node.right and level_node.next:
                    level_node.right.next = level_node.next.left
                
                # 移动到下一节点
                level_node = level_node.next
            
            # 处理下一层，当前层的最左节点就是下一层的根
            cur = cur.left
        
        return root

• 时间复杂度: O(n), n为节点个数
• 空间复杂度: O(1)