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

tag: tree, depth-first-search

11/16/2015 update

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        DFS(root, nullptr);
    }
    TreeNode * DFS(TreeNode* root, TreeNode * tail){
        if(root == nullptr) return tail;
        TreeNode * right = DFS(root->right, tail);
        TreeNode * left = DFS(root->left, right);
        root->left = nullptr;
        root->right = left;
        return root;
    }
};

用一个栈，维护深搜的顺序。

先序遍历。

注意处理输入为空的情况。

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    stack<TreeNode *> s;
    void flatten(TreeNode *root) {
        if(root == NULL){
            return;
        }
        if(root->left == NULL && root->right == NULL && s.empty() == true){
            return;
        }
        if(root->right != NULL){
            s.push(root->right);
        }
        if(root->left != NULL){
            root->right = root->left;
            root->left = NULL;
            flatten(root->right);
        }
        else{//root->left == NULL
            root->right = s.top();
            s.pop();
            flatten(root->right);
        }
    }
};