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

描述

该题来自于力扣第116题

分析

最简单的思路就是层次遍历，然后每层连接就好了。这里介绍另一种方法。

树类问题一般是大问题化解小问题，该题也是如此，但是稍微有些不同，首先这么看，对于某个结点root，首先连接左右节点，即root.left.next = root.right，如果用这种思路递归的话，会少一些连线，如下图所示：

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

1. 1作为root结点，将2,3连接；
2. 2作为root结点，将4,5连接
3. 3作为root结点，将6,7连接

可以看到完成后，5和6之间少一个连线，这时回到以2作为root结点的情况，因为2有next，若将root.right.next = root.next.left，不就将5,6连起来了嘛。

所以递归时，做两件事：
1. root.left.next = root.right
2. root.right.next = root.next.left

再递归左右子树就行。

代码

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        if root is None:
            return
        if root.left is not None:
            root.left.next = root.right
            if root.next is not None:
                root.right.next = root.next.left
        self.connect(root.left)
        self.connect(root.right)
        return root