题目描述
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。
要求不能创建任何新的结点,只能调整树中结点指针的指向。
注意:
需要返回双向链表最左侧的节点。
参考链接:https://www.nowcoder.com/questionTerminal/947f6eb80d944a84850b0538bf0ec3a5?f=discussion
public TreeNode convert(TreeNode root) {
if(root == null) return null;
Stack<TreeNode> stack = new Stack<>();
TreeNode p = root;
TreeNode pre = null;
boolean isFirst = true;
while(p != null || !stack.isEmpty()) {
while(p != null) {
stack.push(p);
p = p.left;
}
p = stack.pop();
if(isFirst) {
root = p;
pre = p;
isFirst = false;
} else {
pre.right = p;
p.left = pre;
pre = p;
}
p = p.right;
}
return root;
}