题解 | #二叉搜索树与双向链表#
二叉搜索树与双向链表
http://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5
解题步骤：
1）用递归得到二叉搜索树的中序遍历结果并存入列表 order里。注意：这里列表中存的是每个节点而非value
2)遍历列表order并生成双向链表。在这里要注意index=0和len(order)-1时的操作。
边界用例：
二叉树为None或只有一个节点时
# class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # # @param pRootOfTree TreeNode类 # @return TreeNode类 # class Solution: def Convert(self , pRootOfTree ): def inorder(root,order): if root ==None: return None inorder(root.left, order) order.append(root) #[list] order里加入的是一个节点而非value inorder(root.right,order) if not pRootOfTree: return None list_order=[] inorder(pRootOfTree, list_order) if len(list_order)==1: return pRootOfTree for i in range(len(list_order)): if i==0: list_order[i].left=None else: list_order[i].left=list_order[i-1] if i==len(list_order)-1: list_order[i].right=None else: list_order[i].right=list_order[i+1] return list_order[0] # write code here
