Python 两种方法实现

方法一：使用额外空间，中序遍历按大小保存树节点，再处理左右指针的指向

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