题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

题解1:使用辅助数组

图示引自:牛客313925129号

代码

void inOrder(TreeNode* root, vector<TreeNode*> v) {
	if(!root) return;
    inOrder(root->left, v);
    v.push_back(root);
    inOrder(root->right, v);
}
TreeNode* Convert(TreeNode* pRootOfTree) {
	if (!pRootOfTree) return pRootOfTree;
    if(!pRootOfTree) return NULL;
    vector<TreeNode*> v;
    //中序遍历
    inOrder(pRootOfTree,v);
    //中序遍历的结果存放在数组中，且数组中的元素是有序的
    //注意：size需要减1，因为代码中有v[i+1]
    for(int i =0;i<v.size()-1;i++){
        //节点的right指向前驱节点
        v[i]->right = v[i+1];
        //节点的left指向前驱节点
        v[i+1]->left = v[i];
    }
    return v[0];
}

题解2:采用辅助辅助指针pre和head

代码

void inOrder(TreeNode* root, TreeNode*& pre, TreeNode*& head) {
    if (!root) return;
    //先序遍历
    inOrder(root->left, pre, head);
    //访问根节点
    if (pre)
        pre->right = root;
    else
        head = root;
    root->left = pre;
    pre = root;
    //访问右子树
    inOrder(root->right, pre, head);
}
TreeNode* Convert(TreeNode* pRootOfTree) {
    if (!pRootOfTree) return NULL;
    TreeNode* pre = NULL, * myhead = NULL;
    //中序遍历
    inOrder(pRootOfTree, pre, myhead);
    return myhead;
}