剑指offer-刷题笔记-中难题-JZ36 二叉搜索树与双向链表

class Solution {
public:
    vector InOrderList;
    void inorder(TreeNode* root)
    {
        //中序遍历-左根右
        if(!root)
        {
            return;
        }
        //左
        if(root->left)
        {
            inorder(root->left);
        }
        //根
        InOrderList.push_back(root);
        //右
        if(root->right)
        {
            inorder(root->right);
        }
    }
    
    TreeNode* Convert(TreeNode* pRootOfTree) {
        //中序遍历-左根右
        //树中节点的左指针需要指向前驱
        //树中节点的右指针需要指向后继
        if(!pRootOfTree)
        {
            return nullptr;
        }
        inorder(pRootOfTree);
        for(int i = 0;i < InOrderList.size()-1;i++)
        {
            InOrderList[i]->right = InOrderList[i+1];
            InOrderList[i+1]->left = InOrderList[i];
        }
        
        return InOrderList[0];
    }
};