二叉搜索树与双向链表
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
为了让您更好地理解问题，以下面的二叉搜索树为例：
image
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
image
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
题目分析
二叉搜索树的中序遍历就是有序序列，而中序遍历是先访问当前节点的左子树，在访问当前节点，最后访问当前节点的右子树；要形成双向链表，就需要将左子树最大的和当前节点连起来，将右子树最小的和当前节点连起来，最后首尾相连，如下图所示：
image
道理我们都懂，但是......
image
足足写了差不多两个小时，心态都崩了......
言归正传，现在来详细说一下这个魔改中序遍历。
- 魔改中序遍历的目的：使得当前节点的左节点是一段双向链表，右节点也是一段双向链表，同时将左节点最大的和右节点最小的分别和根节点拼接
- 遍历第一步：对左节点也做同样的魔改中序遍历，左节点魔改中序遍历返回的结果是左子树最大的数leftMax
- 遍历第二步：对右节点也做同样的魔改中序遍历，右节点魔改中序遍历返回的结果是右子树最大的数rightMax
- 遍历第三步：获取右子树最小的数，root.right.left.left....... -> rightMin
- 遍历第四步：leftMax和root相连、rightMin和root相连
- 遍历第五步，将当前树的最大值rightMax返回给父节点的魔改中序遍历
这么说可能有点抽象（递归），下面放一下这题的代码：
public class Solution {
public Node treeToDoublyList(Node root) {
if(root == null) return null;
// 使得根节点形成双向有序链变，并得到树的最大值
Node rightMax = solve(root);
// 获取树的最小值
Node leftMin = root;
while(leftMin.left != null){
leftMin = leftMin.left;
}
// 收尾相连，形成循环链表
leftMin.left = rightMax;
rightMax.right = leftMin;
return leftMin;
}
public Node solve(Node root) {
if(root == null) return null;
// 使得左子树形成有序双向链表，并返回左子树最大的节点
Node leftMax = solve(root.left);
if(leftMax != null){
// 如果左子树不为空，左子树最大的节点必然存在
// 就连接在根节点的左边
leftMax.right = root;
root.left = leftMax;
}
// 如果右子树存在，就是右子树形成有序双向链表
if(root.right != null){
Node rightMax = solve(root.right);
// 返回右子树最大的值，同时也是当前树的最大值
// 获取右子树最小值，右子树最小值连接在root的右边
Node rightMin = getLeftMin(root.right);
rightMin.left = root;
root.right = rightMin;
return rightMax;
// 在右子树不为空的时候返回右子树最大值给root的父节点
// 否则直接返回root（自身就是当前树最大值）
}else{
return root;
}
}
public Node getLeftMin(Node root){
if(root == null) return null;
Node tmp = root;
while(tmp.left != null){
tmp = tmp.left;
}
return tmp;
}
}
完事啦~
网友评论