今天來(lái)優(yōu)化下之前實(shí)現(xiàn)過(guò)的鏈接下一個(gè)右側(cè)節(jié)點(diǎn)算法听诸，同時(shí)將Ⅰ和Ⅱ做了合并。
題目介紹
給定任意一個(gè)二叉樹(shù)蚕泽，填充它的next節(jié)點(diǎn)晌梨，指向下一個(gè)右側(cè)節(jié)點(diǎn)，最右側(cè)節(jié)點(diǎn)指向null须妻。
看下圖吧：
二叉樹(shù)-填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針Ⅱ-題目.png
實(shí)現(xiàn)思路
今天的實(shí)現(xiàn)思路是借助按層遍歷樹(shù)仔蝌，同時(shí)又稍微做了調(diào)整。
核心思路為：
1.算法利用兩個(gè)隊(duì)列荒吏，一個(gè)當(dāng)前層的節(jié)點(diǎn)隊(duì)列敛惊，一個(gè)是下一層的節(jié)點(diǎn)隊(duì)列。
2.每次遍歷當(dāng)前層隊(duì)列绰更，不斷的從隊(duì)列中取出元素瞧挤，然后設(shè)置nent指向的節(jié)點(diǎn)。
3.另外將當(dāng)前層的非空子節(jié)點(diǎn)加如到下一層的節(jié)點(diǎn)隊(duì)列动知。
4.最終遞歸處理下一層的節(jié)點(diǎn)隊(duì)列皿伺。
該算法的時(shí)間復(fù)雜度和空間復(fù)雜度都不是很好，只是換一種思維來(lái)實(shí)現(xiàn)而已盒粮。
實(shí)現(xiàn)代碼
public class SolutionConnect2 {
public Node connect(Node root) {
if (null == root) {
return null;
}
Queue<Node> currentQueue = new LinkedList<>();
currentQueue.add(root);
connect(currentQueue);
return root;
}
private void connect(Queue<Node> currentQueue) {
if (currentQueue.size() == 0) {
return;
}
Queue<Node> childrenQueue = new LinkedList<>();
Node leftMostNode = currentQueue.remove();
while (null != leftMostNode) {
if (leftMostNode.left != null) {
childrenQueue.add(leftMostNode.left);
}
if (leftMostNode.right != null) {
childrenQueue.add(leftMostNode.right);
}
Node node = null;
if(currentQueue.size()>0){
node = currentQueue.remove();
leftMostNode.next = node;
}
leftMostNode = node;
}
connect(childrenQueue);
}
}
算法相關(guān)實(shí)現(xiàn)源碼地址：https://github.com/xiekq/rubs-algorithms
