Leetcode Populating Next Right Pointers in Each Node
10959 ワード
class Solution {
public:
void connect(TreeLinkNode *root) {
dfs(root, NULL);
}
void dfs(TreeLinkNode* root, TreeLinkNode* counter_part_root) {
if (root == NULL) return;
root->next = counter_part_root;
dfs(root->left, root->right);
dfs(root->right, counter_part_root == NULL ? NULL:counter_part_root->left);
}
};似たようなものを作ったことがあるようで、水が出ると
第2ラウンド:
Given a binary tree
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to
NULL . Initially, all next pointers are set to
NULL . Note:
For example,Given the following perfect binary tree,
1
/ \
2 3
/ \ / \
4 5 6 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ / \
4->5->6->7 -> NULL 1 /**
2 * Definition for binary tree with next pointer.
3 * struct TreeLinkNode {
4 * int val;
5 * TreeLinkNode *left, *right, *next;
6 * TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
7 * };
8 */
9 class Solution {
10 public:
11 void connect(TreeLinkNode *root) {
12 if (root == NULL) {
13 return;
14 }
15 connect(root->left, root->right);
16 connect(root->right, NULL);
17 }
18
19 void connect(TreeLinkNode* root, TreeLinkNode* pairNode) {
20 if (root == NULL) {
21 return;
22 }
23 root->next = pairNode;
24
25 connect(root->left, root->right);
26 connect(root->right, pairNode == NULL ? NULL : pairNode->left);
27 }
28 };階層的な方法でJavaで書きます.
1 /**
2 * Definition for binary tree with next pointer.
3 * public class TreeLinkNode {
4 * int val;
5 * TreeLinkNode left, right, next;
6 * TreeLinkNode(int x) { val = x; }
7 * }
8 */
9 public class Solution {
10 public void connect(TreeLinkNode root) {
11 TreeLinkNode que = root;
12 while (que != null) {
13 TreeLinkNode dummyHead = new TreeLinkNode(0);
14 TreeLinkNode last = dummyHead, cur = que;
15
16 while (cur != null) {
17 if (cur.left != null) {
18 last.next = cur.left;
19 last = last.next;
20 }
21 if (cur.right != null) {
22 last.next = cur.right;
23 last = last.next;
24 }
25 cur = cur.next;
26 }
27 que = dummyHead.next;
28 }
29 }
30 }5.21もう1発C++を書いて層ごとに遍歴して、dfsもとても良いと感じます
// 00:48
/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
void connect(TreeLinkNode *root) {
TreeLinkNode dummyHead(0);
TreeLinkNode* clevel = root;
TreeLinkNode* prev = NULL;
while (clevel) {
prev = &dummyHead;
prev->next = NULL;
while (clevel) {
if (clevel->left != NULL) {
prev->next = clevel->left;
prev = clevel->left;
}
if (clevel->right != NULL) {
prev->next = clevel->right;
prev = clevel->right;
}
clevel = clevel->next;
}
clevel = dummyHead.next;
}
}
};