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 flatten(TreeNode* root) {    if (root == nullptr)        return;    stack
     
       sta;    sta.push(root);    TreeNode* lastRoot = root;    while (!sta.empty())    {        root = sta.top();        if (lastRoot != root->right)        {            if (lastRoot != root->left) {                if (root->left != nullptr) {                    sta.push(root->left);                    continue;                }            }            else            {                TreeNode* tempNode = root->right;                root->right = lastRoot;                root->left = nullptr;                TreeNode* endNode = lastRoot;                while (endNode->right != nullptr)                    endNode = endNode->right;                endNode->right = tempNode;            }            if (root->right != nullptr) {                sta.push(root->right);                continue;            }        }        lastRoot = root;        sta.pop();    }}
     

不使用遍历的方法，即不使用栈解决的方法

void flatten(TreeNode *root) {    TreeNode*now = root;    while (now)    {        if (now->left)        {            //Find current node's prenode that links to current node's right subtree            TreeNode* pre = now->left;            while (pre->right)            {                pre = pre->right;            }            pre->right = now->right;            //Use current node's left subtree to replace its right subtree(original right             //subtree is already linked by current node's prenode            now->right = now->left;            now->left = NULL;        }        now = now->right;    }}