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

���定一个二叉树：

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

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

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

示例 1：

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

示例 2：

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

解法一 BFS

直接把 116 题 题的代码复制过来就好，一句也不用改。

利用一个栈将下一层的节点保存。通过pre指针把栈里的元素一个一个接起来。

public Node connect(Node root) {    if (root == null) {        return root;    }    Queue queue = new LinkedList();    queue.offer(root);    while (!queue.isEmpty()) {        int size = queue.size();        Node pre = null;        for (int i = 0; i  0) {                pre.next = cur;            }            pre = cur;            if (cur.left != null) {                queue.offer(cur.left);            }            if (cur.right != null) {                queue.offer(cur.right);            }        }    }    return root;}

解法二

当然题目要求了空间复杂度，可以先到 116 题 看一下思路，这里在上边的基础上改一下。

我们用第二种简洁的代码，相对会好改一些。

Node connect(Node root) {    if (root == null)        return root;    Node pre = root;    Node cur = null;    while (pre.left != null) {        cur = pre;        while (cur != null) {            cur.left.next = cur.right;            if (cur.next != null) {                cur.right.next = cur.next.left;            }            cur = cur.next;        }        pre = pre.left;    }    return root;}

需要解决的问题还是挺多的。

cur.left.next = cur.right;cur.right.next = cur.next.left;

之前的关键代码就是上边两句，但是在这道题中我们无法保证cur.left 或者 cur.right 或者 cur.next.left或者cur.next.right 是否为null。所以我们需要用一个while循环来保证当前节点至少有一个孩子。

while (cur.left == null && cur.right == null) {    cur = cur.next; }

这样的话保证了当前节点至少有一个孩子，然后如果一个孩子为 null，那么就可以保证另一个一定不为 null 了。

整体的话，就用了上边介绍的技巧，代码比较长，可以结合的看一下。

Node connect(Node root) {    if (root == null)        return root;    Node pre = root;    Node cur = null;    while (true) {        cur = pre;        while (cur != null) {            //找到至少有一个孩子的节点            if (cur.left == null && cur.right == null) {                cur = cur.next;                continue;            }            //找到当前节点的下一个至少有一个孩子的节点            Node next = cur.next;            while (next != null && next.left == null && next.right == null) {                next = next.next;                if (next == null) {                    break;                }            }            //当前节点的左右孩子都不为空，就将 left.next 指向 right            if (cur.left != null && cur.right != null) {                cur.left.next = cur.right;            }            //要接上 next 的节点的孩子，所以用 temp 处理当前节点 right 为 null 的情况            Node temp = cur.right == null ? cur.left : cur.right;            if (next != null) {                //next 左孩子不为 null，就接上左孩子。                if (next.left != null) {                    temp.next = next.left;                //next 左孩子为 null，就接上右孩子。                } else {                    temp.next = next.right;                }            }            cur = cur.next;        }        //找到拥有孩子的节点        while (pre.left == null && pre.right == null) {            pre = pre.next;            //都没有孩子说明已经是最后一层了            if (pre == null) {                return root;            }        }        //进入下一层        pre = pre.left != null ? pre.left : pre.right;    } }

解法三

参考 这里.-Concise.-Fast.-What's-so-hard>)。

利用解法一的思想，我们利用 pre 指针，然后一个一个取节点，把它连起来。解法一为什么没有像解法二那样考虑当前节点为 null 呢？因为我们没有添加为 null 的节点，就是下边的代码的作用。

if (cur.left != null) {    queue.offer(cur.left);}if (cur.right != null) {    queue.offer(cur.right);}

所以这里是一样的，如果当前节点为null不处理就可以了。

第二个问题，怎么得到每次的开头的节点呢？我们用一个dummy指针，当连接第一个节点的时候，就将dummy指针指向他。此外，之前用的pre指针，把它当成tail指针可能会更好理解。如下图所示：

cur 指针利用 next 不停的遍历当前层。

如果 cur 的孩子不为 null 就将它接到 tail 后边，然后更新tail。

当 cur 为 null 的时候，再利用 dummy 指针得到新的一层的开始节点。

dummy 指针在链表中经常用到，他只是为了处理头结点的情况，它并不属于当前链表。

代码就异常的简单了。

Node connect(Node root) {    Node cur = root;    while (cur != null) {        Node dummy = new Node();        Node tail = dummy;        //遍历 cur 的当前层        while (cur != null) {            if (cur.left != null) {                tail.next = cur.left;                tail = tail.next;            }            if (cur.right != null) {                tail.next = cur.right;                tail = tail.next;            }            cur = cur.next;        }        //更新 cur 到下一层        cur = dummy.next;    }    return root;}