-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathFlattenBinaryTreeToLinkedList
More file actions
39 lines (33 loc) · 924 Bytes
/
FlattenBinaryTreeToLinkedList
File metadata and controls
39 lines (33 loc) · 924 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
namespace FlattenBinaryTreeToLinkedList {
class Solution {
public:
void doFlatten(TreeNode ** cur, TreeNode * root) {
(*cur)->left = root;
(*cur) = (*cur)->left;
if (root == NULL) {
return;
}
if (root->left) {
doFlatten(cur, root->left);
}
if (root->right) {
doFlatten(cur, root->right);
}
}
void flatten(TreeNode *root) {
if (root == NULL) {
return;
}
TreeNode dummy(-1);
TreeNode * cur = &dummy;
doFlatten(&cur, root);
cur->left = NULL; // mark the end of list
cur = &dummy;
while (cur != NULL) {
cur->right = cur->left;
cur->left = NULL;
cur = cur->right;
}
}
};
}