二叉搜索树与双向链表.md

二叉搜索树与双向链表

知识点：

题目描述

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

解题思路

首先要明确什么是二叉搜索树： 它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

二叉搜索树的中序遍历结果就是其元素从小到大的排序结果，所以基于中序遍历解决此问题。中序遍历的非递归算法如下：

        stack = []
        p = pRootOfTree

        while len(stack) != 0 or p is not None:
            if p is not None:
                stack.append(p)
                p = p.left
            else:
                p = stack[-1]
                del stack[-1]
                print p
                p = p.right

        

代码

这里