114 Flatten Binary Tree to Linked List

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

• Hints: If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

Solution:

// use inorder traversal
class Solution {
public:
    vector<TreeNode*> inorder(TreeNode* root) {
        vector<TreeNode*> res, left, right;
        if ( root == NULL ) return res;
        res.push_back(root);
        if ( root->left != NULL ) left = inorder(root->left);
        if ( root->right != NULL ) right = inorder(root->right);
        int nl = left.size(), nr = right.size();
        for ( int i = 0; i <= nl-1; i++ ) res.push_back(left[i]);
        for ( int i = 0; i <= nr-1; i++ ) res.push_back(right[i]);
        return res;
    }
    void flatten(TreeNode* root) {
        if ( root == NULL ) return;
        vector<TreeNode*> tnodes = inorder(root);
        int n = tnodes.size();
        if ( n <= 1 ) return;
        for ( int i = 0; i <= n-2; i++ ) {
            tnodes[i]->right = tnodes[i+1];
            tnodes[i]->left = NULL;
        }
        return;
    }
};

Use stack:

class Solution {
public:
    void flatten(TreeNode* root) {
        if ( root == NULL ) return;
        stack<TreeNode*> s;
        s.push(root);
        TreeNode *tnode, *last = NULL;
        while ( ! s.empty() ) {
            tnode = s.top();
            s.pop();
            if ( tnode->right != NULL ) s.push(tnode->right);
            if ( tnode->left != NULL ) s.push(tnode->left);
            if ( last != NULL ) { 
                last->right = tnode;
                last->left = NULL;
            }
            last = tnode;
        }
        return;
    }
};