题解 | #二叉搜索树与双向链表#

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
//left就是前驱，right就是后继
//自上向下考虑：left天生前驱，right天生后继，关键就是考虑每次的插入问题
//自下向上考虑：递归，分配root_parent和root。向上归并时：root是root_parent的left时关照root的右边部分；root是root_parent的right时关照root的左边部分。
#include <ios>
class Solution {
  public:
    //后序遍历处理结点
    void Core(TreeNode* root_parent, TreeNode* root) {
        if (root == nullptr)   return;

        //后序
        Core(root, root->left);
        Core(root, root->right);

        TreeNode* root_left = root;
        TreeNode* root_right = root;

        //root是root_parent的left时关照root的右边部分
        if (root == root_parent->left) {
            //root左边不操作，关键找到最右边的结点
            while (root_right->right != nullptr) {
                root_right = root_right->right;
            }
            root_right->right = root_parent;
            root_parent->left = root_right;
            return;
        }

        //root是root_parent的right时关照root的左边部分
        if (root == root_parent->right) {
            //root右边不操作，关键找到最左边的结点
            while (root_left->left != nullptr) {
                root_left = root_left->left;
            }
            root_left->left = root_parent;
            root_parent->right = root_left;
            return;

        }

    }
    TreeNode* Convert(TreeNode* pRootOfTree) {
        //空或者单结点，直接返回
        if (pRootOfTree == nullptr || pRootOfTree->left == nullptr &&
                pRootOfTree->right == nullptr)   return pRootOfTree;

        TreeNode* root_parent = pRootOfTree;

        //pRootOfTree左边
        Core(root_parent, root_parent->left);

        //pRootOfTree右边
        Core(root_parent, root_parent->right);

        //找到双向链表头节点
        TreeNode* pHead = root_parent;
        while (pHead->left != nullptr) {
            pHead = pHead->left;
        }
        return pHead;
    }
};