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

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

实现递归方法将两个左右子树进行相连，递归即刻。

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

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root
        self.connectwithtwonodes(root.left, root.right)
        return root
        
    def connectwithtwonodes(self, left, right):
        if not left or not right:
            return
        left.next = right
        self.connectwithtwonodes(left.left, left.right)
        self.connectwithtwonodes(right.left, right.right)
        self.connectwithtwonodes(left.right, right.left)