[LeetCode] Flatten Binary Tree to Linked List_综合

[Problem]

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]
递归的方法，对于每个结点root：
（1）flatten其左子树的链表，用leftHead和leftTail分别表示该链表的头结点和尾结点；
（2）flatten其右子树的链表，用rightHead和rightTail分别表示该链表的头结点和尾结点；
（3）按照root->leftHead->leftTail->rightHead->rightTail进行拼接，注意要判断左子树链表和右子树链表是不是NULL

[Solution]

class Solution {
      
public:
    // flatten sub-tree
    void subFlatten(TreeNode* &root, TreeNode* &head, TreeNode* &tail){
      
        // null node
        if(root == NULL){
      
            head = NULL;
            tail = NULL;
            return;
        }
   
        // flatten left brunch
        TreeNode* leftHead = NULL;
        TreeNode* leftTail = NULL;
        if(root->left != NULL){
      
            subFlatten(root->left, leftHead, leftTail);
        }
   
        // flatten right brunch
        TreeNode* rightHead = NULL;
        TreeNode* rightTail = NULL;
        if(root->right != NULL){
      
            subFlatten(root->right, rightHead, rightTail);
        }
   
        // merge
        head = root;
        if(leftHead != NULL){
      
            root->right = leftHead;
            if(rightHead != NULL){
      
                leftTail->right = rightHead;
                tail = rightTail;
            }
            else{
      
                tail = leftTail;
            }
        }
        else{
      
            if(rightHead != NULL){
      
                root->right = rightHead;
                tail = rightTail;
            }
            else{
      
                tail = root;
            }
        }
        head->left = NULL;
    }
   
    // flatten
    void flatten(TreeNode *root) {
      
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        TreeNode* head = NULL;
        TreeNode* tail = NULL;
        subFlatten(root, head, tail);
    }
};