嗨，大家好，我是袁小厨（因为酷爱做饭，所以自己考取了厨师证）。之前一直看大家写的博客，学到了很多东西。然后最近萌生了自己写的想法，将自己知道的分享给需要的同学。以后每天会为大家分享leetcode精选题目的各种题解和Python, JS, JQ, CSS, PHP, JAVA的一些小Demo。请大家关注我，一起交流学习吧。

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

• 题目描述
• 递归解法
• • 做题思路
  • 题目代码
• 层次遍历（队列）
• • 做题思路
  • 题目代码
• BFS
• • 做题思路
  • 题目代码
• 总结

题目描述

递归解法

做题思路

这道题的含义意思就是将每层的节点用链表给连接起来，因为这个题目是完美二叉树，所以我们可以利用递归，然后还可以利用层次遍历。递归算法需要注意的地方就是，我们不能忽略了2节点的右孩子和3节点的左孩子这一条线。所以我们需要新建一个函数来进行递归。

题目代码

class Solution { 
    public Node connect(Node root) { 
        if(root==null){ 
            return null;
        }
        //将左右孩子传入函数中
        connectTwoNode(root.left,root.right);
        return root;

        
    }
    public void connectTwoNode(Node node1, Node node2){ 
           if(node1==null||node2==null){ 
               return ;
           }
           node1.next = node2;
           //三种需要连接的情况
           connectTwoNode(node1.left,node1.right);
           connectTwoNode(node2.left,node2.right);
           connectTwoNode(node1.right,node2.left);
    }

}

层次遍历（队列）

做题思路

关于层次遍历的思想大家可以参考这个文章二叉树的层次遍历。然后我们可以直接用层次遍历来做这个题及填充每个节点的右指针2。需要注意的事我们刚才说的递归法不适用做第二题。因为每个节点的孩子情况可能不一样。不是完美二叉树。

题目代码

class Solution { 
    public Node connect(Node root) { 
        //定义一个队列，用于层次遍历
        Queue<Node> queue = new LinkedList<Node>();
        if(root == null){ 
            return root;
        } 
        queue.offer(root);
        while(!queue.isEmpty()){ 
            int size = queue.size();
            //创建一个指针，用于连接该层，注意的是，这个指针的摆放位置，每一层更新一次
            Node temp = new Node(0);
            for(int i = 0 ; i < size ; i++){ 
                Node q = queue.poll();//出列
                temp.next = q;//指针指向该节点
                temp = temp.next;//移动指针
                Node left = q.left;
                Node right = q.right;
                if(left!=null){ 
                    queue.offer(left);
                }
                if(right!=null){ 
                    queue.offer(right);
                }
            }

        }
        return root;        
    }
}

BFS

做题思路

这个算法算是对刚才算法的改进，速度更快，内存更小。主要思想就是设置一个哑结点temp，游离在树之外，temp.next指向该层的头结点。然后一层一层的添加，用一个cur节点进行，定位，然后将其子节点连接起来，然后cur进行移动，再连接其子孩子，然后cur跳入下一层。pre的功能就是用来连接cur的子节点。该题思想和数组的双重循环类似。这个题目的思想是我跟题解里面的一个大神学习的，图也来自与大神。大家可以也可以自己去看一下。BFS题解

题目代码

 public Node connect(Node root) { 
        if (root == null)
            return root;
         //用来定位层
        Node cur = root;
        while (cur != null) { 
           //哑结点，游离在树之外，用来预定位层数
            Node dummy = new Node(0);
            //用来cur的子节点连接起来
            Node pre = dummy;
            //然后开始遍历当前层的链表
            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;
    }

总结

作者：LeetCode
链接：https://leetcode-cn.com/problems/rotate-array/solution/xuan-zhuan-shu-zu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。