Flatten Binary Tree to Linked List

Oct 26, 2017

Given a binary tree, flatten it to a linked list in-place.

For example, Given

        1
/ \
2   5
/ \   \
3   4   6


The flattened tree should look like:

   1
\
2
\
3
\
4
\
5
\
6


void flatten2(TreeNode *root) {
if (root == nullptr) return ;
stack<TreeNode *> st;
vector<TreeNode *> tvec;
while(true) {
while(root){
st.push(root);
tvec.push_back(root);
root = root->left;
}
if (st.empty() ) break;
root = st.top();
st.pop();
root = root->right;
}
int i;
for(i = 0;i < tvec.size() - 1;i++) {
tvec[i]->left = nullptr;
tvec[i]->right = tvec[i+1];
}
tvec[i]->left = nullptr;
tvec[i]->right = nullptr;
}


void flatten(TreeNode* root) {
if (root==NULL) return ;
flatten(root->left);
flatten(root->right);
auto right = root->right;
auto left = root->left;
if (left){
root->right = left;
root->left = NULL;
while(left->right)
left = left->right;
left->right = right;
}
}


TreeNode *last;
void flatten(TreeNode* root) {
if (root==NULL) return ;
flatten(root->right);
flatten(root->left);
root->right = last;
root->left = nullptr;
last = root;
}


void flatten(TreeNode *root) {
while (root) {
if (root->left && root->right) {
TreeNode* t = root->left;
while (t->right)
t = t->right;
t->right = root->right;
}

if(root->left)
root->right = root->left;
root->left = NULL;
root = root->right;
}
}

LeetCodeLeetCodeTree

Word Break

Construct Binary Tree from Preorder and Inorder Traversal