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

 

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

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

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

思路
因为为完美二叉树，所以当左节点不为空时，右节点也不为空，root.left.next=root.right(示例的2，4，6节点)
当root有右侧节点，root.right.next=root.next.left(示例的5节点)
否则root.right.next=None(示例的1,3,7节点)

class Solution:
    def connect(self, root):
        # 不需要判断root.right是否为null
        if root and root.left:
            root.left.next = root.right
            if root.next:
                root.right.next = root.next.left
            else:root.right.next = None
            self.connect(root.left)
            self.connect(root.right)
        return root

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

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

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

我真的晕了，看不出这两道题的任何区别。。。可能不是完美二叉树？？？所以要加入对“右节点空与不空的判断”？？？

dfs，深搜，和上一题的区别是这不是完全二叉树了，所以要注意几个点：

• 可能有右子树，但没有左子树；
• 要用node->next指向堂兄弟时，可能堂兄弟不是左子结点，而可能是右子结点 (5-->7)；
• 需要先找到右边的堂兄弟结点，所以注意两点：
  • 先遍历右子树；
  • 右边堂兄弟可能不存在。。。

# 运行没通过，也没看????
def connect(self, node):
    tail = dummy = TreeLinkNode(0)
    while node:
        tail.next = node.left
        if tail.next:
            tail = tail.next
        tail.next = node.right
        if tail.next:
            tail = tail.next
        node = node.next
        if not node:
            tail = dummy
            node = dummy.next

    def connect(self, root: 'Node') -> 'Node':
        if root == None or (root.left == None and root.right == None):
            return root
        que = [root]
        while que:
            s = len(que)
            for i in range(s):
                temp = que.pop(0)
                if i+1 < s:
                    # 节点的next是当前对列的第一个，说明是右堂兄弟
                    temp.next = que[0]
                else:
                    # 根节点的next是none
                    temp.next = None
                if temp.left != None:
                    que.append(temp.left)
                if temp.right != None:
                    que.append(temp.right)
        return root

 比较好理解，但是最后一句没有看懂。。。

class Solution(object):
    def connect(self, root):
        if not root:
            return
        
        if root.left and root.right:
            root.left.next =root.right
        elif root.left:
            #if do not have root.left, find root.next.left
            root.left.next = self.findnext(root.next)
        if root.right:
            #always find root.next.left
            root.right.next = self.findnext(root.next)
        
        self.connect(root.right)
        self.connect(root.left)
        return root
    
    def findnext(self, curr):
        if not curr: return 
        elif curr.left:
            return curr.left
        elif curr.right:
            return curr.right
        return self.findnext(curr.next)  # ???? 意思是上面的条件都没符合，然后返回的是个空none。

参考：

利用python 完成leetcode 116 填充每个节点的下一个右侧节点指针

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/discuss/?currentPage=1&orderBy=most_votes&query=&tag=solution