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

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
//  二叉搜索树中序遍历线索化  即每个节点的左链域指向中序遍历序列的前驱，右链域指向中序遍历序列的后继
//则需要找到二叉搜索树每个结点的中序遍历的前驱和后继元素，将该节点的左链域和右链域分别指向前驱和后继结点
//再递归的对每一结点执行如上操作。
//同时记录最小结点的地址，用于最终值返回！
#include <cstdlib>
class Solution {
  public:
  //找出前驱结点
    TreeNode* find_inorder_PreNode(TreeNode* root, TreeNode* parent,
                                   TreeNode* grandfather) {
        //若当前节点左孩子为空  则该节点中序遍历前驱节点为其父节点或爷节点或为空
        if (root->left == nullptr) {
            if (parent && root->val > parent->val) {
                return parent;
            } else if (grandfather && root->val > grandfather->val) {
                return grandfather;
            } else {
                return nullptr;
            }
        }
        //否则  该前驱节点为左子树的最右下节点
        TreeNode* pre_node = nullptr;
        TreeNode* temp = root->left;
        while (temp) {
            pre_node = temp;
            temp = temp->right;
        }
        return pre_node;
    }

  //找出后继结点
    TreeNode* find_inorder_PostNode(TreeNode* root, TreeNode* parent,
                                    TreeNode* grandfather) {
        //若当前节点右子树为空  则该节点的中序遍历后继节点为其父节点或爷节点或为空
        if (root->right == nullptr) {
            if (parent && root->val < parent->val) {
                return parent;
            } else if (grandfather && root->val < grandfather->val) {
                return grandfather;
            } else {
                return nullptr;
            }
        }
        //否则 后继节点为该节点右子树的最左下节点
        TreeNode* temp = root->right;
        TreeNode* post_node = nullptr;
        while (temp) {
            post_node = temp;
            temp = temp->left;
        }
        return post_node;
    }

  
    void tranform(TreeNode* root, TreeNode* parent, TreeNode* grandfather) {
        if (root == nullptr) {
            return ;
        }
        TreeNode* origin_left_child_of_root = root->left;//记录原先左孩子 防止覆盖
        TreeNode* origin_right_child_of_root = root->right;//记录原先右孩子 防止覆盖
        root->left = find_inorder_PreNode(root, parent, grandfather);
        root->right = find_inorder_PostNode(root, parent, grandfather);
	  //递归的执行结点左右链域的更新
	  
	  //更新左子树
        tranform(origin_left_child_of_root, root, parent);
	  //更新右子树
	    tranform(origin_right_child_of_root, root, parent);
    }

    TreeNode* Convert(TreeNode* pRootOfTree) {
	  //fisrt_node 记录第一个节点 实则为二叉搜索树最左下节点  更新完毕后 作为最终结点返回
        TreeNode* first_node = pRootOfTree;
        while (first_node && first_node->left) {
            first_node = first_node->left;
        }
        tranform(pRootOfTree, nullptr, nullptr);
        return first_node;
    }
};