嗨，大家好，我是袁小廚（因為酷愛做飯，所以自己考取了廚師證），之前一直看大家寫的博客，學到了很多東西，然后最近萌生了自己寫的想法，將自己知道的分享給需要的同學，以后每天會為大家分享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）
著作權歸作者所有，商業轉載請聯系作者獲得授權，非商業轉載請注明出處，