节点的下一个右侧节点指针 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
写在最后
如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。
最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。
更多推荐
【每日一题】填充每个节点的下一个右侧节点指针 II
发布评论