【每日一题】填充每个节点的下一个右侧节点指针 II

节点的下一个右侧节点指针 II"/>

【每日一题】填充每个节点的下一个右侧节点指针 II

文章目录

• Tag
• 题目来源
• 题目解读
• 解题思路
• • 方法一：BFS
• 其他语言
• • python3
• 写在最后

Tag

【BFS】【树】【2023-11-03】

题目来源

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

题目解读

为二叉树中的每一个节点填充下一个节点。

解题思路

方法一：BFS

本题题目意思明确，我们只需要遍历二叉树每一层的节点，将节点的 next 指针指向同一层的下一个节点即可，属于二叉树层序遍历的基础题。

实现代码

/*
// Definition for a Node.
class Node {
public:int val;Node* left;Node* right;Node* next;Node() : val(0), left(NULL), right(NULL), next(NULL) {}Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}Node(int _val, Node* _left, Node* _right, Node* _next): val(_val), left(_left), right(_right), next(_next) {}
};
*/class Solution {
public:Node* connect(Node* root) {if (root == NULL) return root;queue<Node*> que;que.push(root);Node* currNode, *prevNode;while (!que.empty()) {int size = que.size();for (int i = 0; i < size; ++i) {if (i == 0) {prevNode = que.front(); que.pop();currNode = prevNode;}else {currNode = que.front(); que.pop();prevNode->next = currNode;prevNode = prevNode->next;}if (currNode->left) que.push(currNode->left);if (currNode->right) que.push(currNode->right);}}return root;}
};

复杂度分析

时间复杂度： O ( N ) O(N) O(N)， N N N 为树上的节点数。

空间复杂度： O ( N ) O(N) O(N)。

其他语言

python3

"""
# Definition for a Node.
class Node:def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):self.val = valself.left = leftself.right = rightself.next = next
"""class Solution:def connect(self, root: 'Node') -> 'Node':if root is None:return rootqueue = deque([root])while queue:n = len(queue)last = Nonefor _ in range(n):cur = queue.popleft()if cur.left:queue.append(cur.left)if cur.right:queue.append(cur.right)if last:last.next = curlast = curreturn root

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。