# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def Convert(self, pRootOfTree):
# write code here
if not pRootOfTree:
return pRootOfTree
res = pRootOfTree
while res.left:
res = res.left
pre_node = None
stack = []
while pRootOfTree:
stack.append(pRootOfTree)
pRootOfTree = pRootOfTree.left
while stack:
top = stack.pop()
temp = top.right
if not pre_node:
pre_node = top
else:
pre_node.right = top
top.left = pre_node
pre_node = top
while temp:
stack.append(temp)
temp = temp.left
return res