Flatten Binary Tree to Linked List

http://www.leetcode.com/onlinejudge

Similar to Convert Sorted List to Binary Search Tree.
 If there is only one branch, move that branch to the right, label left NULL, and recursively process the right child.
If there are two sub trees, take off the right subtree, RS; move the left subtree, PL, to the right, and label left NULL; process the new right child PL (the pointer, PR, will point to the last element of the right child after this process). Attached the detached RS to PR, then process on RS.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public://pre-order
    void pre_order(TreeNode * &root){
        if (!root->left && !root->right) return;
        
        if (!root->left){//left is NULL
            root = root->right;
            pre_order(root);
            return;
        }
        if (!root->right){//right is NULL
            //return;
            root->right = root->left;
            root->left = NULL;
            root = root->right;
            pre_order(root);
            return;
        }
        
        //neither children is NULL
       TreeNode* rightRoot = root->right;
        root->right = root->left;
        root->left = NULL;
        root = root->right;
        pre_order(root);
        root->right = rightRoot;
        root = rightRoot;
        pre_order(root);
        return;
        
    }
    void flatten(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (!root) return;
        pre_order(root);
        return;
    }
};