題目：
給定一個(gè)二叉樹
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腾么。
示例：
image.png
輸入：{"$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":null,"next":null,"right":{"$id":"6","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":null,"right":null,"val":7},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"6","left":null,"next":null,"right":{"$ref":"5"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"6"},"val":1}
解釋：給定二叉樹如圖 A 所示，你的函數(shù)應(yīng)該填充它的每個(gè) next 指針砚蓬，以指向其下一個(gè)右側(cè)節(jié)點(diǎn)，如圖 B 所示盆色。
題解：
這道題目和116題不同的是,這道題的樹不是一顆完全二叉樹,上一道題目我們分別介紹了三種方法灰蛙，那么哪些方法還是有用的呢?
層次遍歷的方法肯定是有用的.代碼我們這里不做贅述。
但是遞歸的方法我們就不能直接用了,因?yàn)槲覀儾蝗ゴ_定連接下一層的時(shí)候,節(jié)點(diǎn)是誰,所以加入了一個(gè)輔助函數(shù):findToLinkedNode隔躲。
image.png
class Solution {
private Node findToLinkedNode(Node node) {
if (node == null) return null;
if (node.left != null) return node.left;
if (node.right != null) return node.right;
return findToLinkedNode(node.next);
}
public Node connect(Node root) {
if (root == null) return null;
if (root.left != null) {
if (root.right != null) {
root.left.next = root.right;
} else {
root.left.next = findToLinkedNode(root.next);
}
}
if (root.right != null) {
root.right.next = findToLinkedNode(root.next);
}
connect(root.right);
connect(root.left);
return root;
}
}
