题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
题目链接：牛客网
解题思路
public class Main {
public static class TreeNode {
int val
= 0;
TreeNode left
= null
;
TreeNode right
= null
;
public TreeNode(int val
) {
this.val
= val
;
}
}
public static TreeNode pre
= null
;
public static TreeNode head
= null
;
public static void main(String
[] args
) {
TreeNode root
= new TreeNode(2);
root
.right
= new TreeNode(3);
root
.left
= new TreeNode(1);
printTree(convert(root
));
}
public static TreeNode
convert(TreeNode root
) {
inOrder(root
);
return head
;
}
public static void inOrder(TreeNode node
) {
if (node
== null
) {
return;
}
inOrder(node
.left
);
node
.left
= pre
;
if (pre
!= null
) {
pre
.right
= node
;
}
pre
= node
;
if (head
== null
) {
head
= node
;
}
inOrder(node
.right
);
}
private static void printTree(TreeNode head
) {
while (head
!= null
) {
System
.out
.print(head
.val
+ "->");
head
= head
.right
;
}
System
.out
.println("null");
}
}
测试结果
