【每日一题】填充每个节点的下一个右侧节点指针 II-Toy模板网

这篇具有很好参考价值的文章主要介绍了【每日一题】填充每个节点的下一个右侧节点指针 II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Tag

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

题目来源

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

【每日一题】填充每个节点的下一个右侧节点指针 II,LeetCode每日一题,BFS,树,2023-11-03

题目解读

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

解题思路

方法一：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)$ ， $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 = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if root is None:
            return root
        
        queue = deque([root])
        while queue:
            n = len(queue)
            last = None
            for _ in range(n):
                cur = queue.popleft()
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
                if last:
                    last.next = cur
                last = cur
        return root