二叉搜索树与双向链表分析

符号 阅读:427 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

声明

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

发表评论
搜索
KIKK导航

KIKK导航

排行榜
关注我们

一个IT知识分享的公众号