import java.util.*;
public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree == null) {
return null;
}
TreeNode root = new TreeNode(-1), node = pRootOfTree, pre = root;
Stack<TreeNode> stack = new Stack();
while(!stack.empty() || node != null) {
// 压自己,先处理左节点
while(node != null) {
stack.push(node);
node = node.left;
}
// 处理自己
node = stack.pop();
pre.right = node;
node.left = pre;
pre = node;
// 处理右节点
node = node.right;
}
// 断开与初始节点的链接
root.right.left = null;
return root.right;
}
}