剑指offer26二叉搜索树与双向链表

剑指offer26

1、常规思路--保存到有序数组在更改
中序遍历保存到数组，然后再更改指向
时间复杂度：O(n), 空间复杂度：O(n)
缺点：多次（两次）遍历

个人代码

class Solution {
public:
    vector<TreeNode*>v;
    void midTraverse(TreeNode*pRoot)
    {
        if(!pRoot)
            return;
        midTraverse(pRoot->left);
        v.push_back(pRoot);
        midTraverse(pRoot->right);
    }

    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(!pRootOfTree) return nullptr;
        midTraverse(pRootOfTree);
        for(int i=0;i<v.size()-1;i++)
        {
            v[i]->right=v[i+1];
            v[i+1]->left=v[i];
        }
        v[0]->left=nullptr;
        v[v.size()-1]->right=nullptr;
        return v[0];
    }
};

2、优化，一次遍历
全局保存每次遍历的上一个节点，注意细节头尾节点处理
时间复杂度：O(n) 空间复杂度：O（n）
优点：一次遍历
[2]:https://www.nowcoder.com/profile/396966893/codeBookDetail?submissionId=110301954
[个人代码][2]

class Solution {
public:
    TreeNode* lastNode=nullptr;//保存当前遍历的上一个节点,也会保存最后一个节点（未处理）
    TreeNode* pHead=nullptr;
    void midTraverse(TreeNode*pRoot)
    {
        if(!pRoot)
            return;
        midTraverse(pRoot->left);
        if(lastNode)
            lastNode->right=pRoot; //上一个节点right指向当前节点
        else
            pHead=pRoot; //链表头，第一次节点的上一个节点为空
        pRoot->left=lastNode; //当前节点的left指向上一个节点
        lastNode = pRoot;
        midTraverse(pRoot->right);
    }

    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(!pRootOfTree) return nullptr;
        midTraverse(pRootOfTree);
        lastNode->right=nullptr; //处理最后一个节点right指向空
        return pHead;
    }
};