题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
练习地址
https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5
https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
参考答案
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
private TreeNode mLast;
public TreeNode Convert(TreeNode pRootOfTree) {
if (pRootOfTree == null) {
return null;
}
convertNode(pRootOfTree);
// 我们需要返回头节点
while (mLast.left != null) {
mLast = mLast.left;
}
return mLast;
}
private void convertNode(TreeNode node) {
if (node.left != null) {
convertNode(node.left);
}
node.left = mLast;
if (mLast != null) {
mLast.right = node;
}
mLast = node;
if (node.right != null) {
convertNode(node.right);
}
}
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(logn)。
