/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

/*利用平衡二叉树中序遍历有序的特点，例如：

           10
          /  \
         8   14

维护一个last变量，存储当前双向链表的最后一个节点。当中序遍历到10时，last应该指向8。

将10的left指针指向8，如果8不为NULL，将8的right指针指向10，然后last指向10。
*/
class Solution {
public:
    // 当前双向链表的最后一个节点
    TreeNode* last = NULL;

    TreeNode* convert(TreeNode* root) {
        deal(root);

        // 由last尾节点找双向链表头节点
        TreeNode* head = last;
        while(head != NULL && head->left != NULL)
        {
            head = head->left;
        }
        return head;
    }

    void deal(TreeNode* p)
    {
        if(!p) return;

        TreeNode* cur = p;

        if(cur->left) Convert(cur->left);

        // 调整left、right节点指向
        cur->left = last;
        if(last) last->right = cur;
        last = cur;

        if(cur->right) Convert(cur->right);

    }
};