题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
题解
对二叉搜索树进行中序遍历，可得到递增的顺序，所以在中序遍历时完成相邻两个节点的互指即可。
TreeNode pre = null;
public TreeNode Convert(TreeNode root) {
if (root == null)
return null;
ConvertHelper(root);
// 转换结束，返回双向链表表头
while (root.left != null)
root = root.left;
return root;
}
public void ConvertHelper(TreeNode cur) {
if (cur == null)
return;
ConvertHelper(cur.left);
// 建立双向链表
cur.left = pre;
if (pre != null)
pre.right = cur;
pre = cur;
ConvertHelper(cur.right);
}
网友评论