打卡群刷题总结0814——二叉树展开为链表

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

链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下： struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。 初始状态下，所有 next 指针都被设置为 NULL。

示例：

输入：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

输出：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}

解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。

解题：

1、层次遍历。

代码：

"""# 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 root        ls = [root]        while len(ls) > 0:            tmp = []            while len(ls) > 0:                node = ls.pop(0)                if len(ls) > 0:                    node.next = ls[0]                if node.left:                    tmp.append(node.left)                if node.right:                    tmp.append(node.right)            ls = tmp        return root        

PS：刷了打卡群的题，再刷另一道题，并且总结，确实耗费很多时间。如果时间不够，以后的更新会总结打卡群的题。

PPS：还是得日更呀，总结一下总是好的。