wap蓝天建站,wordpress 批量插件,西地那非片,百度关键词排名突然下降很多二叉搜索树与双向链表
题目链接#xff1a;二叉搜索树与双向链表
解题思路1#xff1a;递归中序遍历
首先题目最后要求的是一个的递增的双向链表#xff0c;而二叉搜索树也是一类非常有特色的树#xff0c;它的根节点大于所有左侧的节点#xff0c;同时又小于所有右侧的…二叉搜索树与双向链表
题目链接二叉搜索树与双向链表
解题思路1递归中序遍历
首先题目最后要求的是一个的递增的双向链表而二叉搜索树也是一类非常有特色的树它的根节点大于所有左侧的节点同时又小于所有右侧的节点如果我们按照左中右去遍历这颗二叉树恰巧得到的就是一个递增序列
题目同时要求不要创建新的节点这样我们就需要在原有树上进行操作树有左右节点指针双向链表有前后两个指针正好一一对应我们修改指针指向结合中序遍历得到一颗递增的双向链表
代码如下 TreeNode* head nullptr;TreeNode* pre nullptr;TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTree nullptr) return nullptr;//递归的结束条件Convert(pRootOfTree-left);//递归到最左节点是最小值if(pre nullptr){//此时pRootOfTree是最左节点是链表的head//初始化head和prehead pRootOfTree;pre pRootOfTree;}else{//pre是每一个pRootOfTree的前驱节点pre-right pRootOfTree;pRootOfTree-left pre;pre pRootOfTree;}Convert(pRootOfTree-right);return head;}解题思路2非递归栈
我们利用栈先进后出的特性来模拟中序遍历出所有元素先让所有左侧的元素进栈再依次取出其父节点再找该节点的右节点将节点进行连接连接方式和上一种思路一样 TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTree nullptr) return nullptr;TreeNode* head nullptr;TreeNode* pre nullptr;stackTreeNode* s;while(pRootOfTree!nullptr || !s.empty()){while(pRootOfTree!nullptr){s.push(pRootOfTree);pRootOfTree pRootOfTree-left;}pRootOfTree s.top();s.pop();if(pre nullptr){head pRootOfTree;pre pRootOfTree;}else{pre-right pRootOfTree;pRootOfTree-left pre;pre pRootOfTree;}pRootOfTree pRootOfTree-right;}return head;}
