Python 两种方法实现
二叉搜索树与双向链表
http://www.nowcoder.com/questionTerminal/947f6eb80d944a84850b0538bf0ec3a5
方法一:使用额外空间,中序遍历按大小保存树节点,再处理左右指针的指向
class Solution: def Convert(self, pRootOfTree): if not pRootOfTree: return None self.tree = [] self.dfs(pRootOfTree) if len(self.tree) == 1: return self.tree[0] for i in range(len(self.tree)): if i == 0: self.tree[i].right = self.tree[i+1] elif i == len(self.tree)-1: self.tree[i].left = self.tree[i-1] else: self.tree[i].left = self.tree[i-1] self.tree[i].right = self.tree[i+1] return self.tree[0] def dfs(self, root): if not root: return self.dfs(root.left) self.tree.append(root) self.dfs(root.right)
方法二:不使用额外空间,在进行中序遍历时,对左右指针指向进行处理
class Solution: def Convert(self, pRootOfTree): if not pRootOfTree: return None root = self.dfs(pRootOfTree, None) while root.left: root = root.left return root def dfs(self, root, last_node): # 额外参数,当前已遍历节点的最大 if not root: return None if root.left: # 处理左子树 last_node = self.dfs(root.left, last_node) # 返回左子树的最大值节点 root.left = last_node # 当前节点的左指针的指向左子树最大值节点 if last_node: # 左子树的最大值节点的右指针指向当前节点 last_node.right = root # last_node = root # 更新已处理节点的最大值节点 if last_node.right: # 处理右子树 last_node = self.dfs(root.right, last_node) return last_node