基本信息

  • 题号：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」类比复习。