leetcode原題鏈接：

116題：填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針

題目描述

給定一個(gè) 完美二叉樹(shù) ，其所有葉子節(jié)點(diǎn)都在同一層，每個(gè)父節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)。二叉樹(shù)定義如下：

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

填充它的每個(gè) next 指針，讓這個(gè)指針指向其下一個(gè)右側(cè)節(jié)點(diǎn)。如果找不到下一個(gè)右側(cè)節(jié)點(diǎn)，則將 next 指針設(shè)置為 NULL。
初始狀態(tài)下，所有 next 指針都被設(shè)置為 NULL。

輸入：root = [1,2,3,4,5,6,7]
輸出：[1,#,2,3,#,4,5,6,7,#]
解釋：給定二叉樹(shù)如圖 A 所示，你的函數(shù)應(yīng)該填充它的每個(gè) next 指針，以指向其下一個(gè)右側(cè)節(jié)點(diǎn)，如圖 B 所示。序列化的輸出按層序遍歷排列，同一層節(jié)點(diǎn)由 next 指針連接，‘#’ 標(biāo)志著每一層的結(jié)束。

示例2
輸入：root = []
輸出：[]

提示：
樹(shù)中節(jié)點(diǎn)的數(shù)量在 [0, 212 - 1] 范圍內(nèi)
-1000 <= node.val <= 1000

進(jìn)階：
你只能使用常量級(jí)額外空間。
使用遞歸解題也符合要求，本題中遞歸程序占用的?？臻g不算做額外的空間復(fù)雜度。

遞歸解法一

解題思路：
這題在遞歸中，主要思考點(diǎn)就是，遞歸左樹(shù)和右樹(shù)時(shí)。不是同一個(gè)頭節(jié)點(diǎn)的子樹(shù)時(shí)，怎么樣把左樹(shù)鏈接到右樹(shù)上去。如上圖中五和六節(jié)點(diǎn)在遞歸過(guò)程中，這兩個(gè)點(diǎn)，并沒(méi)在同一個(gè)遞歸過(guò)程中。就無(wú)法鏈接起來(lái)，因此我們要修改下遞歸過(guò)程，把左右樹(shù)同時(shí)遞歸，這樣在同一個(gè)過(guò)程里，就可以看見(jiàn)兄弟節(jié)點(diǎn)了。代碼演示如下。

  public Node connect(Node root) {if(root == null){return root;}process(root.left,root.right);return root;}public void process(Node root1,Node root2){if(root1 == null || root2 == null){return ;}root1.next = root2;//左樹(shù)內(nèi)部鏈接起來(lái)。process(root1.left,root1.right);//右樹(shù)內(nèi)部鏈接起來(lái)process(root2.left,root2.right);//左樹(shù)和右樹(shù)鏈接起來(lái)。process(root1.right,root2.left);}

遞歸方法二（效率更高）

思路：
我們?cè)谶f歸的過(guò)程中，把層級(jí)結(jié)構(gòu)也進(jìn)行遞歸，每次把層級(jí)結(jié)構(gòu)和左樹(shù)的右節(jié)點(diǎn)放進(jìn)map 中，在遍歷到右樹(shù)時(shí)，根據(jù)層級(jí)來(lái)判斷，拿到左樹(shù)，然后把它們相連，就完成了遞歸。和上面相比，少了一次遞歸。效率會(huì)增加很多.代碼演示。

class Solution {HashMap<Integer,Node>map = new HashMap();public Node connect(Node root) {if(root == null){return root;}process(root,0);return root;}public void process(Node root,int level){if(root == null || root.left == null){return;}root.left.next = root.right;v6(root.left,level + 1);v6(root.right,level + 1);if(map.get(level) != null){Node cur = map.get(level);cur.next = root.left;}map.put(level,root.right);}}

二叉樹(shù)專(zhuān)題

從前序與中序遍歷序列構(gòu)造二叉樹(shù)（java）

leetcode二叉樹(shù)中的最大路徑和(java)

二叉樹(shù)的遞歸–判斷二叉樹(shù)是否是滿(mǎn)二叉樹(shù)（java實(shí)現(xiàn)）