二叉搜索树与双向链表

符号阅读：904 2020-10-21 17:08:00 评论：0

题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

解:这道题其实是一道中序遍历的题，需要注意的是把当前子树最大的节点返回到上一层。

下面解法中注意的是，第二个参数要加引用。因为我们需要返回上一个结点本身，而不是修改结点中的值。如果不加引用，第二个参数其实是一个复制的指针指向要返回的节点，而外层的指针并未改变，下面可以看一个例子

/* 
struct TreeNode { 
    int val; 
    struct TreeNode *left; 
    struct TreeNode *right; 
    TreeNode(int x) : 
            val(x), left(NULL), right(NULL) { 
    } 
};*/ 
class Solution { 
public: 
    TreeNode* Convert(TreeNode* pRootOfTree) 
    { 
        if(pRootOfTree==nullptr) 
        { 
            return nullptr; 
        } 
        TreeNode *pre=nullptr; 
        ConvertImplement(pRootOfTree,pre); 
 
        TreeNode* res = pRootOfTree; 
        while(res ->left) 
            res = res ->left; 
        return res; 
    }; 
    //pre返回为左子树最大的结点 
    void ConvertImplement(TreeNode* pRootOfTree,TreeNode*& pre) 
    { 
        if(pRootOfTree==nullptr) 
        { 
            return; 
        } 
         
        ConvertImplement(pRootOfTree->left,pre); 
         
        pRootOfTree->left=pre; 
         
        if(pre) 
        { 
            pre->right=pRootOfTree; 
        } 
        pre=pRootOfTree; 
        //右 
        ConvertImplement(pRootOfTree->right,pre); 
    } 
};

void test(int *p, int *pre) 
{ 
    pre = p; 
} 
int main() 
{ 
    char *p = "12222"; 
    string s1(p, 2); 
    son *s = new son; 
    base *b=nullptr; 
    delete(b); 
 
    int i = 1; 
    int *ptr = nullptr; 
    test(&i, ptr); 
}

这里的ptr还是nullptr

标签:加密算法 C++面试

声明

1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，请转载时务必注明文章作者和来源，不尊重原创的行为我们将追究责任；3.作者投稿可能会经我们编辑修改或补充。