【LeetCode-中等题】117. 填充每个节点的下一个右侧节点指针 II

题目

方法一：常规方法参考链接

【LeetCode-中等题】116. 填充每个节点的下一个右侧节点指针

方法二：不使用额外的空间，把每一层看做一个链表，将其链接起来

class Solution {
    public Node connect(Node root) {
        if(root == null) return null;
        Node cur = root;
        Node dummy = null;
        //此循环切换层级
        while(cur != null){
             dummy = new Node(-1);//哑结点
             Node pre = dummy;//pre  用作前置指针 用于将同一层的链接起来
             //此循环处理同一层的cur
             while(cur!=null){
                 if(cur.left!=null){//链接左孩子
                     pre.next = cur.left;
                     pre = pre.next;
                 }
                 if(cur.right!=null){//链接右孩子
                     pre.next = cur.right;
                     pre = pre.next;
                 }
                 cur = cur.next; //切换下一个同层节点
            }
            //切换下一层
            cur  = dummy.next;
         }
          return root;
       }
    }


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29