泗塘新村街道网站建设,wordpress中文语言包,标志设计图案,wordpress 周生生今日份题目#xff1a;
输入一棵二叉搜索树#xff0c;将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点#xff0c;只能调整树中节点指针的指向。
示例 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于…今日份题目
输入一棵二叉搜索树将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点只能调整树中节点指针的指向。
示例 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表第一个节点的前驱是最后一个节点最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。 题目思路
根据二叉搜索树的性质我们知道中序遍历可以得到树节点的从小到大的排序那我们就在中序递归遍历的基础上改变链表。使用pre节点记录上个节点的位置使用cur节点记录当前节点的位置使用head节点记录链表头部的位置然后每次让pre节点和cur节点互相指pre左cur右最后让head和pre节点相互指就能得到结果链表了。具体看代码注释。
补充中序遍历
树的一种遍历方法遍历顺序是左-根-右如果左或右是树而非节点那么就在子树中继续左根右最后递归得到顺序。
int inOrder(Node* root)
{if(root-left) inOrder(root-left);return root-val;if(root-right) inOrder(root-right);
}
代码
/*
// Definition for a Node.
class Node {
public:int val;Node* left;Node* right;Node() {}Node(int _val) {val _val;left NULL;right NULL;}Node(int _val, Node* _left, Node* _right) {val _val;left _left;right _right;}
};
*/
class Solution
{
public:Node *pre,*head;void dfs(Node* cur) {if(curNULL) return;//中序遍历dfs(cur-left);//左边pre右边cur二者相连pre继续向后走直到结束if(pre!NULL) pre-rightcur;else headcur;cur-leftpre;precur;dfs(cur-right);}Node* treeToDoublyList(Node* root) {if(rootNULL) return NULL;dfs(root);//中间连好了头尾相连head-leftpre;pre-righthead;return head;}
};提交结果 欢迎大家在评论区讨论如有不懂的部分欢迎在评论区留言
更新不易宝子们点个赞支持下谢谢
