Flatten a binary tree to a fake "linked list" in pre-order traversal.

Here we use the_right_pointer in TreeNode as the_next_pointer in ListNode.

Notice

Don't forget to mark the left child of each node to null. Or you will get Time Limit Exceeded or Memory Limit Exceeded.

Have you met this question in a real interview?

Yes

Example

              1
               \
     1          2
    / \          \
   2   5    =
>
    3
  / \   \          \
 3   4   6          4
                     \
                      5
                       \
                        6

Challenge

Do it in-place without any extra memory.

/**

* Definition of TreeNode:

* class TreeNode {

* public:

* int val;

* TreeNode *left, *right;

* TreeNode(int val) {

* this->val = val;

* this->left = this->right = NULL;

* }

* }

*/

class Solution {

public:

/\*\*

 \* @param root: a TreeNode, the root of the binary tree

 \* @return: nothing

 \*/

void flatten\(TreeNode \*root\) {

    // write your code here

    while \(root\) {

        if \(root->left\) {

            TreeNode\* pre = root->left;

            while \(pre->right\)

                pre = pre->right;

            pre->right = root->right;

            root->right = root->left;

            root->left = NULL;

        }

        root = root->right;

    }

}

};