114. Flatten Binary Tree to Linked List

My solution is create a helper function that intakes a root and return the last node in the flatten list. So the tree can be flatten by flattening left and right child respectively and move the left child to right and connect the right child to the last node in the left flatten child.

1:  class Solution {  
2:  public:  
3:    void flatten(TreeNode* root) {  
4:      if (root == NULL) return;  
5:      helper(root);  
6:    }  
7:    TreeNode *helper(TreeNode *root) {  
8:      if (root->left == NULL && root->right == NULL) return root;  
9:      TreeNode *left = NULL;  
10:      TreeNode *right = NULL;  
11:      if (root->left != NULL) {  
12:        left = helper(root->left);  
13:        left->right = root->right;  
14:        root->right = root->left;  
15:        root->left = NULL;  
16:        if (left->right != NULL) {  
17:          return helper(left->right);  
18:        } else {  
19:          return left;  
20:        }  
21:      } else {  
22:        return helper(root->right);  
23:      }  
24:    }  
25:  };  

Also, my solution is quite slow (only beats 12%). It can be improved as following:

1:  class Solution {  
2:  public:  
3:    void flatten(TreeNode* root) {  
4:      helper(root);  
5:    }  
6:    TreeNode *helper(TreeNode *root) {  
7:      if (root == NULL) return NULL;  
8:      TreeNode *l_end = helper(root->left);  
9:      TreeNode *r_end = helper(root->right);  
10:      if (l_end) {  
11:        TreeNode *tmp = root->right;  
12:        root->right = root->left;  
13:        root->left = NULL;  
14:        l_end->right = tmp;  
15:      }  
16:      return r_end ? r_end : (l_end ? l_end : root);  
17:    }  
18:  };