Flatten Binary Tree to Linked List

• Time : O(n)
• Space : O(1)

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 TreeNode* helper(TreeNode* A) {
    TreeNode* res = A;
    if(A->left == NULL and A->right == NULL) return res;
    if(A->left == NULL and A->right != NULL) return helper(res->right);
    if(A->left != NULL and A->right == NULL) {
        swap(res->left, res->right);
        return helper(res->right);
    }
    TreeNode* l = A->left;
    TreeNode* r = A->right;
    res->right = res->left = NULL;
    res->right = l;
    TreeNode* leftTail = helper(l);
    leftTail->right = r;
    return helper(r);
 }
TreeNode* Solution::flatten(TreeNode* A) {
    helper(A);
    return A;
}