前言有一个二叉搜索树，如何在不创建任何新节点的情况下将其转换为有序双向链表？本文将把这个算法分享给大家。欢迎有兴趣的开发者阅读本文。思路分析在二叉树中，每个节点都有两个指向子节点的指针。在双向链表中，每个节点也有两个指针，分别指向上一个节点和下一个节点。这两个节点的结构非常相似。二叉搜索树是一种有序的数据结构。它的左子节点的值总是小于父节点的值，右子节点的值总是大于父节点的值。那么，当我们将二叉搜索树转换为有序双向链表时：将原来指向左子节点的指针调整为指向链表中前一个节点的指针。原来指向右子节点的指针调整为指向链表中下一个节点的指针。如何转换接下来，让我们考虑如何转换。由于转换后的链表是有序的，所以我们可以按顺序遍历树中的每个节点，因为我们在实现二叉搜索树-中序遍历一文中总结了它的特点，从小到大依次访问每个节点。下面用一个具体的例子来进一步分析。当我们对根节点进行中序遍历时，我们可以把树看成三部分（如下图所示）：值为10的节点和值为6的根节点的右边左子树的根节点值为14的子树根据排序链表的定义，值为10的节点将与其左子树中的最大节点（值为8的节点）相连，并且还会和右子树中最小的节点（值为12的节点）链接起来，如下图，它被拆分为根节点，左右子树，我们转换把左子树和右子树都变成一个双向链表然后和根节点链接起来，整个二叉查找树就变成了一个有序的双向链表。思路总结按照中序遍历的顺序，当我们遍历到根节点（值为10的节点）时，其左子树已经转换为排序链表，当它是中的最后一个节点时链表中，当前值最高的节点。我们将值为8的节点链接到根节点，此时链表的最后一个节点是10。然后遍历转换后的右子树，将根节点与右子树中最小的节点链接起来。分析到这里，相信大家都看到了，左右子树节点的转换过程和遍历过程是一样的，所以我们可以用递归来解决问题。将左子树构造成双向链表，将头节点返回到左子树双向链表的最后一个节点如果左子树链表不为空，则将当前根节点追加到左子树链表中构造右子树变成双链表，返回头节点如果右子树链表不为空，则将链表追加到根节点，根据左子树链表是否为空判断返回节点完成。导出函数treeToLinkedList(root:BinaryTreeNode|null|undefined):BinaryTreeNode|null{if(root==null)返回null;如果（root.left==null&&root.right==null）返回根；子树构造成双链表，返回链表的头节点constleftTree=treeToLinkedList(root.left);//遍历左子树的双链表，找到其右子树的最后一个节点letpNode=leftTree;while(pNode!=null&&pNode.right!=null){pNode=pNode.right;}//如果最后一个节点存在，则将两个节点相互连接if(pNode){//将其右子树连接到根节点pNode.右=根；//连接根节点的左子树root.left=pNode;}//将右子树构造成双链表并返回链表的头节点constrightTree=treeToLinkedList(root.right);//如果右子树链表不为空，则将链表附加到根节点if(rightTree!=null){rightTree.left=root;root.right=右树；}返回leftTree!=null？leftTree:root;}testUseCase我们使用文中列举的例子来验证上面的代码是否能正确解决问题。consttree:BinaryTreeNode={key:10,left:{key:6,left:{key:4},right:{key:8}},right:{key:14,left:{key:12},right:{键:16}}};constlinkedListResult=treeToLinkedList(tree);控制台日志（linkedListResult）；执行结果如下，树的左右指针指向的节点都正确改变了。image-20221222165006886示例代码请移步本文所用代码完整版：BinaryTreeToDoublyLinkedList.tsbinaryTreeToDoublyLinkedList-test.ts
