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

https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/

给定一个二叉树

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

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

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

进阶：

你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。

示例：

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]

解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。

提示：

树中的节点数小于 6000
100 <= node.val <= 100

通过次数24,724 | 提交次数49,413

Second Try

2020-07-17

用链表的思路来解决，竟然变得非常简单，思路也很清晰（当然更简单的还是用BFS一波带走，只是空间复杂度不符合要求）。

每一次考虑当前节点的下一层，使用dummy node在前面带路，后面一路链接下去就可以了。而dummy节点的下一个节点，刚好就是下一层的起始点。事情就这样完美解决了。

# 用链表的思路来解决
class Solution(object):
    def connect(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        if not root:
            return root 
        curr = root 
        while curr:
            head = curr 
            lead = dummy = Node(None)  # next level 
            while head: # consider about the next level 
                if head.left:
                    lead.next = head.left 
                    lead = lead.next 
                if head.right:
                    lead.next = head.right 
                    lead = lead.next 
                head = head.next     
            curr = dummy.next 
        return root 

执行用时：36 ms, 在所有 Python 提交中击败了82.55%的用户
内存消耗：15.2 MB, 在所有 Python 提交中击败了100.00%的用户

First Try

2020-07-17

非递归版本，细节有点多，容易出错
一是各种左节点和右节点可存在可不存在，判断多
二是left和right需要能够翻跃循环的间隔。为了简化拼写搞了left和right，凑巧发现了解决方法。

平时要解决，还是用上BFS层序遍历，或者是Second Try里链表的方式。

"""
# 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
        """
        # 非递归版本，细节有点多，容易出错
        # 一是各种左节点和右节点可存在可不存在，判断多
        # 二是left和right需要能够翻跃循环的间隔。 为了简化拼写搞了left和right，凑巧发现了解决方法。
        left_most = root 
        while left_most and (left_most.left or left_most.right):
            lead = left_most
            while lead:
                if lead.left and lead.right:
                    lead.left.next = lead.right
                if lead.right or lead.left: 
                    right = lead.right or lead.left  # 可以跨越循环,防止中间某个节点没有子节点，而左右相邻皆有
                if lead.next:
                    left = lead.next.left or lead.next.right 
                    if left and right:  # 左节点可能也不存在，因此也需要能够被跳过
                        right.next = left
                        right = None  
                lead = lead.next 
            left_most = left_most.left or left_most.right
            while left_most and (not (left_most.left or left_most.right)):
                left_most = left_most.next 
        return root  

执行用时：44 ms, 在所有 Python 提交中击败了42.18%的用户
内存消耗：15.3 MB, 在所有 Python 提交中击败了100.00%的用户

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

Second Try​

First Try​

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

Second Try

First Try