思路:中序遍历的同时构造双向链表。

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

    TreeNode* convert(TreeNode* root) {
        if (!root) return NULL;

        inorder(root);

        //中序遍历完成后，root会指向最左边即最小的节点
        while (root && root->left) root = root->left;

        return root;
    }

    void inorder(TreeNode* root)
    {
        if (!root) return;

        inorder(root->left);

        if (pre) pre->right = root; //前一个节点的右边指向当前节点
        root->left = pre;           //当前节点的左边指向前一个节点构成双向链表
        pre = root;                 //最后让pre指针指向当前节点，开始下一轮dfs

        inorder(root->right);
    }
};