您好,登錄后才能下訂單哦!
給定一個(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。
示例:
輸入:{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}
輸出:{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}
解釋:給定二叉樹(shù)如圖 A 所示,你的函數(shù)應(yīng)該填充它的每個(gè) next 指針,以指向其下一個(gè)右側(cè)節(jié)點(diǎn),如圖 B 所示。
提示:
你只能使用常量級(jí)額外空間。
使用遞歸解題也符合要求,本題中遞歸程序占用的??臻g不算做額外的空間復(fù)雜度。
題目要求使用O(1)的額外空間,所以考慮類似BFS的算法。
因?yàn)闃?shù)是完美的,那么當(dāng)前這一層和上一層的關(guān)系是緊密的,體現(xiàn)在上一層節(jié)點(diǎn)cur存在next不為null那么當(dāng)前層cur.left也存在next并且cur.right也存在next,可以根據(jù)示例圖理解。每一層從上一層的最左邊節(jié)點(diǎn)的左孩子開(kāi)始遍歷。
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
Node pre=root;
while(pre!=null){
Node cur=pre;
while(cur!=null){
if(cur.left!=null)
cur.left.next=cur.right;
if(cur.right!=null&&cur.next!=null){
cur.right.next=cur.next.left;
}
cur=cur.next;
}
pre=pre.left;
}
return root;
}
}
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。