「脸书」刷起来 116 ～ 每个节点指向右边的节点

基本信息

• 题号：116
• 题厂：脸书
• 难度系数：中

已知一个标准的二叉树，让每个节点指向它右边的节点。初始时，下一个节点默认为空；如果该节点本身就是最右节点，那就还是指向空。

例如 root = [1,2,3,4,5,6,7]
返回 [1,#,2,3,#,4,5,6,7,#]

解题思路

• 了解题目叫我们干什么之后，首先观察一下题目给出的二叉树结构：

# 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

• 本题里，二叉树除了由常见的左右节点，还多了一个 next 节点。而我们要做的就是把 next 节点指向正确。
• 同层节点指向问题，就是一个「BFS」遍历问题，而和「BFS」配套的数据结构是「queue」。

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        # 如果节点为空，可以直接提前返回
        if not root:
            return root
        # 如果节点不为空，初始化 que 开始遍历   
        que = [root]

        # 每一层用 for 循环便利，如果当前节点有同层右边还有节点，就把该节点的 next 指向右边的节点
        # 遍历同时生成下一层参加遍历的 que，按照左右顺序放入 nextLevel
        while que:
            nextLevel = []
            for i in range(len(que)):
                if i + 1 < len(que):
                    que[i].next = que[i + 1]
                if que[i] and que[i].left:
                    nextLevel.append(que[i].left)
                if que[i] and que[i].right:
                    nextLevel.append(que[i].right)
            
            que = nextLevel


        return root

Constraints

• The number of nodes in the tree is in the range [0，2^12 - 1].
• -1000 <= Node.val <= 1000

做题前和考官讨论会不会有空节点

Big O

• 时间复杂度：O（n），每个节点走一遍；
• 空间复杂度：O（logn）。stack 长度巅峰时为二叉树最后一层的长度，即 logn，因为题目告知这是一个标准二叉树。

测试

• 节点为空时

……

总结

• 以「BFS + queue」 基础知识展开的考点题。思路很容易想到，属于中档偏简单档。
• 本题和 #117 是同一系列。
• 本题可作为 「BFS + queue」模板题定期复习，同时结合 「DFS + stack」类比复习。