[LeetCode] 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

DFS solution:

class Solution {
private:
    // This returns the last node on the right 
    TreeNode* flatTree(TreeNode *root) {
        if(!root->left && !root->right) return root;
        TreeNode *l = NULL; TreeNode *r = NULL;
        if(root->right)  
        {
            r = flatTree(root->right);
        }        
        if(root->left)
        {
            l = flatTree(root->left);
            TreeNode *t = root->right;
            root->right = root->left;
            root->left = NULL;
            l->right = t;
        }
        return r?r:l;
    }
public:
    void flatten(TreeNode *root) {
        if(!root) return;
        flatTree(root);
    }
};

Note: Each node's right child points to the next node of a pre-order traversal

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