Leetcode：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/》GitHub：https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_29_treeToDoublyList/Solution.javaConvertbinarysearchtreetodoublylinkedlist》题目描述：输入二叉搜索树，将二叉搜索树转化为有序的循环双向链表，要求不能创建新的节点，只能调整节点指针在树中的指向。为了让大家更好的理解这个问题，以下面这个二叉搜索树为例：难度：中我们要将这棵二叉搜索树转化为一个双向链表，链表中的每个节点都有前驱和后继指针。对于双向链表，第一个节点的前身是最后一个节点，最后一个节点的后继者是第一个节点。图中是low表示由上述二叉搜索树转换而来的链表。“head”表示指向链表中元素最小的节点。特别是，我们希望就地完成转换。转换完成后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。您还需要返回指向链表中第一个节点的指针。解题思路：本文的解法基于性质：二叉搜索树的中序遍历是递增序列。将二叉搜索树转换为“有序循环双向链表”，它由三个元素组成：有序链表：节点应该按照从小到大的顺序排序，所以应该使用中序遍历来访问树的节点“从小到大”最大”。双向链表：在构造相邻节点的引用关系时，设置前驱节点pre和当前节点cur，不仅要构造pre.right=cur，还要构造cur.left=pre。循环链表：如果链表的头节点是head，尾节点是tail，那么应该构造head.left=tail和tail.right=head。算法流程：dfs(cur)：递归中序遍历；终止条件：当节点cur为空时，表示跳过叶子节点，直接返回；递归左子树，即dfs(cur.left)；建立链表：当pre为Empty时：表示访问链表的头节点，记录为head；当pre不为空时：修改双向节点引用，即pre.right=cur,cur。左=前；savecur：updatepre=cur，即后继节点的节点curpre；递归右子树，即dfs(cur.right)；treeToDoublyList(root)：特例处理：如果节点root为空，直接返回；初始化：空节点pre；转换为双向链表：调用dfs(root)；构建循环链表：顺序遍历完成后，head指向头节点，pre指向尾节点，所以修改head和pre的双向节点引用；返回值：只返回链表的头节点head；复杂度分析：时间复杂度0(N)：N为二叉树的节点数，中序遍历需要访问所有节点。空间复杂度O(N)：最坏情况下，当树退化为链表时，递归深度达到N，系统使用0(N)栈空间。packagecom.nateshao.sword_offer.topic_29_treeToDoublyList;/***@dateCreatedby邵通杰on2021/12/215:31*@微信公众号程序员千语*@个人网站www.nateshao.cn*@bloghttps://nateshao.gitee.io*@GitHubhttps://github.com/nateshao*@Giteehttps://gitee.com/nateshao*说明：二叉搜索树和双向链表*/publicclassSolution{//1.Inorder，recursive，从解题大哥Nodepre，头；publicNodetreeToDoublyList(Noderoot){//边界值if(root==null)returnnull;dfs(root);//主题需要头尾连接head.left=pre;pre.right=head;//返回头节点returnhead;}voiddfs(Nodecur){//递归结束条件if(cur==null)return;dfs(cur.left);//如果pre为空，表示是第一个节点，头节点，然后使用head保存头结点，以备后面返回if(pre==null)head=cur;//不为空则为中间结点。并pre保存上一个节点，//让上一个节点的右指针指向当前节点elseif(pre!=null)pre.right=cur;//让当前节点的左指针指向父节点,甚至变成双向链表cur.left=pre;//保存当前结点，供下层递归创建pre=cur;dfs(cur.right);}/***思路：定义一个链表的尾节点，并递归处理左右子树，最后返回链表的头节点=lastlist;while(pHead!=null&&pHead.left!=null)pHead=pHead.left;returnpHead;}??publicNodecoverNode(Noderoot,Nodelastlist){if(root==null)returnnull;Nodecur=root;if(cur.left!=null)coverNode(cur.left,lastlist);cur.left=lastlist;如果(lastlist!=null)lastlist.right=cur;lastlist=cur;if(cur.right!=null)lastlist=coverNode(cur.right,lastlist);returnlastlist;}classNode{publicintval;publicNodeleft;publicNoderight;publicNode(){}publicNode(int_val){val=_val;}publicNode(int_val,Node_left,Node_right){val=_val;left=_left;right=_right;}}}
