[LeetCode] Flatten Binary Tree to Linked List

Problem Statement (link):

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

Analysis:
Observe the flattened tree closely, we find that it's basically a pre-order traversal transformation. However, what's more than that is we need to link the tree properly, as in-place transformation is required.

The idea is: before we traverse the left sub-tree of a node, we use a pointer to save the right child, because when we finished left sub-tree traversal, the root node's right child would be the current left child. Additionally, we would need another pointer prev to store the previous visited node, as later when we need to link the node to it's previous node.

Code:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    // Recursive preorder traversal
    void flatten(TreeNode *root) {
        TreeNode *prev = NULL;
        recur(root, prev);
    }
    void recur(TreeNode *node, TreeNode *&prev) {
        if (node==NULL) return;
        TreeNode *saveRightNode = node->right;

        if (prev!=NULL) {
            prev->right=node;
            prev->left=NULL;
        }
        prev=node;
        recur(node->left, prev);
        recur(saveRightNode, prev);
    }
};