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

【LetMeFly】116.填充每个节点的下一个右侧节点指针

力扣题目链接：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

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

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

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

 

示例 1：

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

示例 2:

输入：root = []
输出：[]

 

提示：

• 树中节点的数量在 [0, 212 - 1] 范围内
• -1000 <= node.val <= 1000

 

进阶：

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

方法一：层次遍历

其实这道题只需要将二叉树层序遍历，然后遍历的同时记录一下上一个遍历到的节点是什么。

如果这个节点和上一个节点位于同一层，则将上一个节点的next指向这一个节点。

有关二叉树的层序遍历可以参考LeetCode 102. 二叉树的层序遍历

• 时间复杂度$O(N)$，其中$N$是节点的个数
• 空间复杂度$O(M)$，其中$M$是最后一层的节点的数量

AC代码

C++

typedef pair<Node*, int> pii;
class Solution {
public:
    Node* connect(Node* root) {
        if (!root)
            return root;
        queue<pii> q;
        q.push({root, 1});
        int lastLayer = 0;
        Node* lastNode;
        while (q.size()) {
            auto[thisNode, thisLayer] = q.front();
            q.pop();
            if (thisLayer == lastLayer) {
                lastNode->next = thisNode;
            }
            lastNode = thisNode;
            lastLayer = thisLayer;
            if (thisNode->left)
                q.push({thisNode->left, thisLayer + 1});
            if (thisNode->right)
                q.push({thisNode->right, thisLayer + 1});
        }
        return root;
    }
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/125821076