剑指offer（二叉搜索树与双向链表（Python））在线编程

站在巨人的肩膀上，风景这边独好；
亲自爬上巨人的肩膀，才知风景为什么这么美。

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

文章图片

解题思路
吐槽我刷的牛客网就只有文字描述没有图啊！！表示看不懂… 网上搜索看到这张图片之后开始构思解题思路。当时瞄到这么一张图：

文章图片

然后就开始顺着这张图的思路想解决办法了：用中序遍历和递归，且以这张图为第一步，后续的左右子树均按照图示的思路来做，并且前后不用任何中间节点。但慢慢发现，如果用递归，在不新建任何中间节点的情况下，我只能实现到：4==6==8==10==16==14==12，并且图示提供的思路也不够精确。
遂求助网络，但得到的解法均需要新建辅助节点，且绝大多数代码不够简练。在牛客网该题下大家的讨论中倒是有不错的思路，只是没有配文的情况下还需要点时间理解。鉴于自己没查到该题精简且详细的解题思路，我就露个拙，实现Python解法，并配上我的理解。
思路

核心算法依旧是中序遍历
不是从根节点开始，而是从中序遍历得到的第一个节点开始
定义两个辅助节点listHead(链表头节点)、listTail(链表尾节点)。事实上，二叉树只是换了种形式的链表；listHead用于记录链表的头节点，用于最后算法的返回；listTail用于定位当前需要更改指向的节点。了解了listHead和listTail的作用，代码理解起来至少顺畅80%。
提供我画的算法的过程图，有点丑，但有助于理解（帮你们画了，你们就不用画啦），另外图中右上角步骤三应该是“2”标红，“2”和“1”中间的连接为单线黑~~~

文章图片

Python代码

class Solution: def __init__(self): self.listHead = None self.listTail = None def Convert(self, pRootOfTree): if pRootOfTree==None: return self.Convert(pRootOfTree.left) if self.listHead==None: self.listHead = pRootOfTree self.listTail = pRootOfTree else: self.listTail.right = pRootOfTree pRootOfTree.left = self.listTail self.listTail = pRootOfTree self.Convert(pRootOfTree.right) return self.listHead

【剑指offer（二叉搜索树与双向链表（Python））】稍微多说一句，其实这段代码也就5行，5行中2行是中序遍历的代码，分别是第8、16行；3行是更改节点指向的代码，为13-15行。9-11行的if语句只有在中序遍历到第一个节点时调用，自此之后listHead不变，listTail跟随算法的进度。为了更清楚的展示，给出中序遍历的代码如下。对比可以看出来，实际上只是中序遍历中的第八行代码被上述的if-else语句替代了，仅此而已。

class Solution: def __init__(self): self.array = [] def midOrder(self, root): if not root: return self.array self.midOrder(root.left) self.array.append(root.val) self.midOrder(root.right)

不想一个节点一个节点的验证得到的双向链表是否正确，可以用如下方法验证链表的正向序和反向序：

def printList(self, head): while head.right: print(head.val, end=" ") head = head.right print(head.val) while head: print(head.val, end= " ") head = head.left

最后的最后，写代码一般需要在自己的编辑器上跑通，才会提交到网站上，所以这里给出全套的代码，用以验证方法的正确与否：

class Solution: def __init__(self): self.listHead = None self.listTail = None# 将二叉树转换为有序双向链表 def Convert(self, pRootOfTree): if pRootOfTree==None: return self.Convert(pRootOfTree.left) if self.listHead==None: self.listHead = pRootOfTree self.listTail = pRootOfTree else: self.listTail.right = pRootOfTree pRootOfTree.left = self.listTail self.listTail = pRootOfTree self.Convert(pRootOfTree.right) return self.listHead# 获得链表的正向序和反向序 def printList(self, head): while head.right: print(head.val, end=" ") head = head.right print(head.val) while head: print(head.val, end= " ") head = head.left# 给定二叉树的前序遍历和中序遍历，获得该二叉树 def getBSTwithPreTin(self, pre, tin): if len(pre)==0 | len(tin)==0: return Noneroot = TreeNode(pre[0]) for order,item in enumerate(tin): if root .val == item: root.left = self.getBSTwithPreTin(pre[1:order+1], tin[:order]) root.right = self.getBSTwithPreTin(pre[order+1:], tin[order+1:]) return rootclass TreeNode: def __init__(self, x): self.left = None self.right = None self.val = xif __name__ == '__main__': solution = Solution() preorder_seq = [4,2,1,3,6,5,7] middleorder_seq = [1,2,3,4,5,6,7] treeRoot1 = solution.getBSTwithPreTin(preorder_seq, middleorder_seq) head = solution.Convert(treeRoot1) solution.printList(head)#4 #/\ #26 #/ \/ \ # 13 57