python实现leetcode之117. 填充每个节点的下一个

解题思路

使用队列进行广度优先遍历，附带上深度
如果该节点的深度与前一节点的深度相同，就指向前一节点
所以必须先右后左入队列

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

代码

"""
# 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 root:
            queue = [(root, 0)]
            prev_node, prev_depth = None, None
            while queue:
                node, lv = queue.pop()
                if lv == prev_depth:
                    node.next = prev_node
                prev_node, prev_depth = node, lv
                if node.right: queue.insert(0, (node.right, lv+1))
                if node.left: queue.insert(0, (node.left, lv+1))
        return root