题目描述
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。
要求不能创建任何新的结点,只能调整树中结点指针的指向。
中序遍历,迭代解法(Java)
在中序遍历的框架上修改代码即可
维护一个 pre 指针,指向当前结点前面的一个节点,每次遍历的时候,指向下面操作
- pre 的 right 指向当前结点
- 当前结点的 left 指向 pre
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode convert(TreeNode root) {
if (root == null) return null;
TreeNode pre = null, p = root;
Deque<TreeNode> st = new LinkedList<>();
while (p != null || !st.isEmpty()) {
while (p != null) {
st.addLast(p);
p = p.left;
}
TreeNode node = st.pollLast();
if (node.right != null) p = node.right;
node.left = pre;
if (pre != null) pre.right = node;
pre = node;
}
while (pre.left != null) pre = pre.left;
return pre;
}
}