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

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

题解

在当前节点的下一层设置一个哑节点(仅用于标记)，串联下一层的左右节点，当当前节点还有next节点(之前串联起来的)，使当前节点跳转到next节点，之后，本层遍历完毕，把哑节点的next节点赋值给当前节点(换层)，创建新哑节点继续处理即可。

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public 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; //cur我们可以把它看做是每一层的链表 Node cur = root; while (cur != null) { //遍历当前层的时候，为了方便操作在下一 //层前面添加一个哑结点（注意这里是访问 //当前层的节点，然后把下一层的节点串起来） Node dummy = new Node(0); //pre表示访下一层节点的前一个节点 Node pre = dummy; //然后开始遍历当前层的链表 while (cur != null) { if (cur.left != null) { //如果当前节点的左子节点不为空，就让pre节点 //的next指向他，也就是把它串起来 pre.next = cur.left; //然后再更新pre pre = pre.next; } //同理参照左子树 if (cur.right != null) { pre.next = cur.right; pre = pre.next; } //继续访问这样行的下一个节点 cur = cur.next; } //把下一层串联成一个链表之后，让他赋值给cur， //后续继续循环，直到cur为空为止 cur = dummy.next; } return root; } } 

本文地址：https://blog.csdn.net/Rush6666/article/details/108846051