题意

给定一棵二叉搜索树，通过改变指针而不创建新节点将这棵二叉搜索树转化为排序的双向链表。

分析

考虑分治的做法，如果已经可以把左右子树规模的子问题解决，那么如何解决当前问题。
如果左右子树都被转化为双向链表，那么只要让左子树变成的链表尾的右指针指向 root，root的左指针指向该节点，右子树最左的左指针指向 root，root 右指针指向该节点。
base case 是 trivial的。

/**
 * 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* convert(TreeNode* root) {
        if(root == NULL)return root;
        if(root->left == NULL && root->right == NULL)return root;

        TreeNode* left = convert(root->left);
        TreeNode* right = convert(root->right);
        if(left != NULL){
           TreeNode* p = left;
           while(p->right != NULL)p = p->right;
           p->right = root;
           root->left = p;
        }
        if(right != NULL){
            right->left = root;
            root->right = right;
        }

        return root->left == NULL ? root : left;
    }
};