1. 递归处理左右子树，返回子树的最大值和最小值（即：最右侧结点，最左侧结点）
2. 分情况讨论

/**
 * 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)  return NULL;
        auto side = dfs(root);
        return side.first;
    }

    pair<TreeNode*, TreeNode*> dfs(TreeNode *root)
    {
        if (!root->left && !root->right)  return {root, root};
        if (root->left && root->right)
        {
            auto lside = dfs(root->left), rside = dfs(root->right);
            root->left = lside.second;
            lside.second->right = root;
            root->right = rside.first;
            rside.first->left = root;
            return {lside.first, rside.second};
        }
        else if (root->left)
        {
            auto lside = dfs(root->left);
            root->left = lside.second;
            lside.second->right = root;
            return {lside.first, root};
        }
        else if (root->right)
        {
            auto rside = dfs(root->right);
            root->right = rside.first;
            rside.first->left = root;
            return {root, rside.second};
        }
    }
};