题目描述
二叉搜索树与双向链表
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
思路:
其实就是 将跟与 叶子 中间加入 链表的关系。
java实现:
public class Solution {
TreeNode head = null;
TreeNode realHead = null;
public TreeNode Convert(TreeNode pRootOfTree) {
ConvertSub(pRootOfTree);
return realHead;
}
private void ConvertSub(TreeNode pRootOfTree) {
if(pRootOfTree==null) return;
ConvertSub(pRootOfTree.left);
if (head == null) {
head = pRootOfTree;
realHead = pRootOfTree;
} else {
head.right = pRootOfTree; //head的右侧 连下一个
pRootOfTree.left = head; //下一个的 左侧 连 head 形成双向链表
head = pRootOfTree; //head 往后挪
}
ConvertSub(pRootOfTree.right);
}
}
墨予 发布了92 篇原创文章 · 获赞 5 · 访问量 2588 私信 关注