## Monday, September 28, 2015

### LeetCode OJ - Flatten Binary Tree to Linked List

Problem:

Solution:

First, note that, the signature do not allow a return, which means the root of the tree node must be unchanged. That's calls for pre-order.

Next, if we do a pre-order traversal, and then modify the tree at the same time, we are done.

In order to stitch the list together, I need the end of the list, that's why I introduced a helper function for that purpose, it returns the end of the list of the subtree we are processing.

Code:

#include "stdafx.h"

#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

{
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution
{
TreeNode* flattenWithLast(TreeNode* root)
{
TreeNode* left = root->left;
TreeNode* right = root->right;
root->left = NULL;
root->right = NULL;
TreeNode* last = root;
if (left != NULL)
{
last->right = left;
last = flattenWithLast(left);
}
if (right != NULL)
{
last->right = right;
last = flattenWithLast(right);
}
return last;
}
public:
void flatten(TreeNode* root) {
if (root == NULL)
{
return;
}
flattenWithLast(root);
}
};
};

{
Solution solution;
TreeNode a(1);
TreeNode b(2);
TreeNode c(3);
TreeNode d(4);
TreeNode e(5);
TreeNode f(6);
a.left = &b;
b.left = &c;
b.right = &d;
a.right = &e;
e.right = &f;
solution.flatten(&a);
TreeNode* curr = &a;
while (curr != NULL)
{
cout << curr->val;
curr = curr->right;
}
cout << endl;
return 0;
}