二叉搜索树与双向链表

二叉搜索树与双向链表

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

​

首先，双向链表和二叉树从数据结构的变量上讲，是同样的，，每次都得把当前节点的左孩子指向之前的节点，之前节点的右孩子指向当前节点

/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { }};*/class Solution {public: //pre必须是一个引用，随着全局改变，而改变 void inorder(TreeNode* cur,TreeNode*&pre) { if(cur==NULL)return; inorder(cur->left,pre); //当前节点的左孩子是pre节点 cur->left=pre; //如果pre不为NULL，将当前节点赋值给pre的右孩子 if(pre!=NULL)pre->right=cur; //更新pre值 pre=cur; inorder(cur->right,pre); } TreeNode* Convert(TreeNode* pRootOfTree) { if(pRootOfTree==NULL)return NULL; TreeNode* pre=NULL; inorder(pRootOfTree,pre); //转化成功之后pRootOfTree节点不在最前端，需要一直遍历到最前端 //pRootOfTree->left 不等于NUll时进入循环 while(pRootOfTree->left!=NULL)pRootOfTree=pRootOfTree->left; return pRootOfTree; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。