大家好呀，今天為大家帶來的LeetCode的題目是：LeetCode116.填充每個節點的下一個右側節點指標，屬于一道關于二叉樹的中等難度的題目，
題目
分析
看完題目后看一下提示內容，一個是只能使用常量級的額外空間，一個是可以使用遞回的方法來解決該題目，要是不通過提示的話，看完這個題目的第一反應的解法就是層次遍歷，題目要求的是每一層都建立指標，那么我們只需要逐層遍歷即可，
通過提示我們知道還有第二種解法就是遞回方法，
解法一：層次遍歷
這種是最直觀的，也是思維難度較低的一種演算法，就是從根節點逐層遍歷，在遍歷的程序中建立指標，
層次遍歷是基于廣度優先搜索的，與廣度優先搜索不同的是，廣度優先搜索每次只會取出一個節點，而層次遍歷還會把該層元素都獲取到，這樣我們就可以實作在遍歷中修改每個節點的next指標，同時也將其子節點加入到佇列中
解法二：遞回
對于要建立指標的兩個節點來說，只有兩種情況：
- 第一種：這兩個節點屬于同一個父節點，這樣我們只需要：node.left.next=node.right
- 第二種：這兩個節點屬于不同的父節點，這種情況下無法直接連接，所以我們需要從上往下進行建立，利用本層以及建立好的指標來為下一層建立連接，
具體做法就是，從根節點開始遍歷（根節點不需要建立連接），然后根據這層的連接關系，開始為下一層建立連接，首先先建立第一種情況的連接，然后利用該層的連接針對第二種情況進行建立連接，
需要注意的是當我們為第N層節點建立next指標時，處于第N-1層，當第N層節點的next指標全部建立完成后，移至第N層，開始建立第N+1層節點的next指標，
代碼實作
解法一：層次遍歷
public Node connect(Node root) {
if (root == null) {
return root;
}
// 初始化佇列同時將第一層節點加入佇列中，即根節點
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
// 外層的 while 回圈迭代的是層數
while (!queue.isEmpty()) {
// 記錄當前佇列大小
int size = queue.size();
// 遍歷這一層的所有節點
for (int i = 0; i < size; i++) {
// 從隊首取出元素（移除）
Node node = queue.poll();
// 連接，注意最后一個不需要進行連接，所以要有一個判斷，
if (i == size - 1) {
node.next = queue.peek();
}
// 將下一層的節點放進去
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
// 回傳根節點
return root;
}
}
解法二：
public Node connect(Node root) {
if (root == null) {
return root;
}
// 從根節點開始
Node leftmost = root;
while (leftmost.left != null) {
// 遍歷這一層節點組織成的鏈表，為下一層的節點更新 next 指標
Node head = leftmost;
while (head != null) {
// 第一種情況，兩個需要建立的子節點有共同的父節點
head.left.next = head.right;
// 第二種情況，此時需要借助上一層的指標來進行建立
if (head.next != null) {
head.right.next = head.next.left;
}
// 指標向后移動，即從該層開始往右邊進行移動
head = head.next;
}
// 去下一層的最左的節點，由于建立了該層的連接所以只需要從最左節點開始遍歷即可
leftmost = leftmost.left;
}
return root;
}
最后
- 如果覺得看完有識訓，希望能給我點個贊，這將會是我更新的最大動力，感謝各位的支持
- 歡迎各位關注我的公眾號【java冢狐】，專注于java和計算機基礎知識，保證讓你看完有所識訓，不信你打我
- 如果看完有不同的意見或者建議，歡迎多多評論一起交流，感謝各位的支持以及厚愛，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/176697.html
標籤：其他
上一篇：2020 ccf 華為Serverless作業負載預測baseline score=0.0846分享
下一篇：走進多執行緒(一):什么是執行緒