根据二叉搜索树的性质，我们很容易想到用中序遍历的方法
一个比较蠢的方法是我们用中序遍历检索，然后将检索到的每个结点都存放在链表中
然后将这些结点全部双向连接起来
但是这样会产生O(N)的空间开销，没有必要，我们只关注链表的最后一个结点和当前结点
然后将最后一个结点和当前结点连接起来即可
中序遍历始终采用左-----根-----右的方式连接
比如我们定义一个函数，输入一个根节点，和当前情况下链表的最后一个结点，然后输出中序遍历之后的最后一个结点
例如我们定义 def Find_Lastnode(self,pRoot,None)：
宏观上来讲，我们输入了整棵树的根节点，并且将链表最后一个结点设置为None，那么就会输出整个列表的最后一个结点
然后我们顺着最后一个结点，不断的寻找它的左节点直到头结点，最后输出即可
具体过程可以如下表示
我们将根节点设置为当前结点
pCur = pRoot
如果左子树存在，那么就把左子树的根节点丢进去，这样会输出左子树产生的列表的最后一个结点
#左
if pRoot.left:
Lastnode = self.Find_Lastnode(pRoot.left,Lastnode)
找到了左子树的最后一个结点之后，把它指向当前结点，即输入的这棵树的根节点
Lastnode.right = pCur
假设这个Lastnode不是一个空节点的话，我们还需要将pCur指向Lastnode
pCur.left = Last
#中
然后将最后一个结点跟新为当前结点
Lastnode = pCur
这样就完成了根结点与左子树的连接，且链表的最后一个结点现在是根节点
再对右子树进行遍历，这里很巧妙的一点是，由于我们永远采用左-------中-------右的顺序，
所以我们检索到右子树的第一个结点就是右子树中最小的结点，我们直接将它与链表最后一个结点，即根节点相连即可
当然，说到底，这也是中序遍历的本质，也不算特别巧妙，但是不熟练的话，就很难想通
if pRoot.right:
Lastnode = self.Find_Lastnode(pRoot.,Lastnode)
最后返回的就是整个链表的最后一个结点啦
return Lastnode
然后再对这个它不停地去寻找左结点，直到找到头结点就停止，然后输出的就是我们需要的链表头啦！
网友评论