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

描述

分析

对比力扣第116题的区别在于，该题不再是完美二叉树了，首先看下之前的做法：

root.left.next = root.right
root.right.next = root.next.left

对于第一步来说，如果root依然有左右节点，那么一模一样，否则不用连接；

对于第二步，本质是A.next = B，如果root.right存在，那么A就是root.right，否则看root.left是否存在，存在的话，就是root.left，要不然就不用连接，B的取值就要考虑一些情况，如果root.next没有left,right那么就找root.next.next，直到找到含有left,right的结点node，如果找到了这样的node，显然以node.left为最高优先级，即node.left存在，则B = node.left，否则B = node.right。找到了A,B，只需令A.next = B就好。

代码

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if root is None:
            return
        if root.left and root.right:
            root.left.next = root.right
        if root.next:
            left_ = root.right if root.right else root.left
            node, right_ = root.next, None
            while node:
                if node.left:
                    right_ = node.left
                    break
                elif node.right:
                    right_ = node.right
                    break
                else:
                    node = node.next
            if left_ and right_:
                left_.next = right_
        self.connect(root.right)
        self.connect(root.left)
        return root