-
Notifications
You must be signed in to change notification settings - Fork 6
/
convert_binary_tree_to_linked_list.cpp
54 lines (43 loc) · 2.22 KB
/
convert_binary_tree_to_linked_list.cpp
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void flatten(TreeNode* root) {
/*
1 1 1
/\ / \ \
2 5 => 2 5 =>. 2
/ \ \ \ \ \
3 4 6 3 6 3
\ \
4 4
\
5
\
6
In the above problem, we have to traverse in preorder fashion and change left subtree to right subtree. Once we do that, we have to fix the right subtree below the changed left subtree.
*/
if(!root or (!root->left and !root->right)) return; //important to traverse back from leaf node to the parent node.
if(root->left) { //check first if we have a left subtree from current root
flatten(root->left); //recurse until the leftmost child in current tree
TreeNode *tempRight = root->right; //store the right child of original tree into a temporary variable
root->right = root->left; //stick left half to right half(check node 3, 4 in diagram)
root->left = NULL; //set the left of original tree to NULL
TreeNode *current = root->right; //stick right half of original tree(tempRight) below new right subtree
while(current->right != NULL) {
current = current->right;
}
current->right = tempRight;
}
flatten(root->right);
}
};