题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
解:这道题其实是一道中序遍历的题，需要注意的是把当前子树最大的节点返回到上一层。
下面解法中注意的是，第二个参数要加引用。因为我们需要返回上一个结点本身，而不是修改结点中的值。如果不加引用，第二个参数其实是一个复制的指针指向要返回的节点，而外层的指针并未改变，下面可以看一个例子
/* 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
原创文章，作者：Maggie-Hunter，如若转载，请注明出处：https://blog.ytso.com/17540.html