剑指Offer 36.二叉搜索树和双向链表
LeetCode
剑指Offer 36.二叉搜索树和双向链表
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。
为了让您更好地理解问题,以下面的二叉搜索树为例:
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
解法1:链表拼接
解题思路:
看下图:
所有关于树的问题都可以用分治的思想来解决,本题要求我们将二叉树转变成双向的有序循环链表,因为二叉搜索树左孩子的结点值永远比右孩子结点的值要小,所以我们把左孩子看作一条链表,把右孩子看作另一条链表,我们要做的就是合成这两条链表
我们先定义链表
class NodeList{
Node head; //链表头部
Node rear; //链表尾部
public NodeList(Node head, Node rear)
{
this.head = head;
this.rear = rear;
}
};
如上图所示,我们把每一个叶子结点单独设置为一个链表
public void init(Node root, HashMap<Node,NodeList> map)
{
if(root==null)
return;
if(root.left==null && root.right==null) //左右孩子都为空的结点就是叶子结点
{
NodeList list = new NodeList(root,root); //链表的头部和尾部都是自身
map.put(root,list);
return;
}
init(root.left,map);
init(root.right,map);
}
合并a,b链表(父节点的左孩子代表的结点和右孩子代表的结点,如上图的结点4)要进行以下操作
- a链表头部的前驱结点要指向b链表尾部
- b链表尾部的后继结点要指向a链表头部
- a链表尾部要指向父结点,父结点左孩子指向a链表尾部
- b链表头部要指向父节点,父节点右孩子指向b链表头部
但是要考虑父节点只有左孩子或者只有右孩子的情况
- 当父节点只有左孩子,那父节点就是新链表的尾部
- 当父节点只有右孩子,那父节点就是新链表的头部
合并链表的代码如下:
if(root.left==null && root.right==null) //左右孩子都为空就返回
return;
if(root.left!=null && !map.containsKey(root.left)) //左孩子还没合成链表
treeToDoublyList(root.left,map);
if(root.right!=null && !map.containsKey(root.right))//右孩子还没合成链表
treeToDoublyList(root.right,map);
if(root.left==null) //如前面所说明
{
NodeList rightlist = map.get(root.right); //右孩子的链表
root.right = rightlist.head; //当前结点作为新链表的头结点,拼接到链表头部上
rightlist.head.left = root; //双向
root.left = rightlist.rear; //双向
rightlist.rear.right = root; //尾部指向新的头结点
map.put(root, new NodeList(root,rightlist.rear));
return;
}
if(root.right==null) //同理
{
NodeList leftlist = map.get(root.left);
root.left = leftlist.rear; //当前结点作为新链表的尾结点,拼接到尾部
leftlist.rear.right = root; //双向
root.right = leftlist.head; //后继指针指向链表头节点
leftlist.head.left = root; //头结点指向链表新的尾结点
map.put(root,new NodeList(leftlist.head,root));
return;
}
//如上图的操作(New操作),改变两个链表的头尾结点指向
NodeList leftlist = map.get(root.left);
NodeList rightlist = map.get(root.right);
leftlist.rear.right = root;
root.left = leftlist.rear;
rightlist.head.left = root;
root.right = rightlist.head;
leftlist.head.left = rightlist.rear;
rightlist.rear.right = leftlist.head;
map.put(root,new NodeList(leftlist.head,rightlist.rear));
return;
完整代码:
class NodeList{
Node head;
Node rear;
public NodeList(Node head, Node rear)
{
this.head = head;
this.rear = rear;
}
};
class Solution {
public Node treeToDoublyList(Node root) {
if(root==null)
{
return root;
}
if(root.left==null&&root.right==null)
{
root.left=root;
root.right=root;
return root;
}
HashMap<Node,NodeList> map = new HashMap<Node,NodeList>();
init(root,map);
treeToDoublyList(root,map);
NodeList res = map.get(root);
return res.head;
}
public void treeToDoublyList(Node root, HashMap<Node,NodeList> map)
{
if(root.left==null && root.right==null)
return;
if(root.left!=null && !map.containsKey(root.left))
treeToDoublyList(root.left,map);
if(root.right!=null && !map.containsKey(root.right))
treeToDoublyList(root.right,map);
if(root.left==null)
{
NodeList rightlist = map.get(root.right);
root.right = rightlist.head;
rightlist.head.left = root;
root.left = rightlist.rear;
rightlist.rear.right = root;
map.put(root, new NodeList(root,rightlist.rear));
return;
}
if(root.right==null)
{
NodeList leftlist = map.get(root.left);
root.left = leftlist.rear;
leftlist.rear.right = root;
root.right = leftlist.head;
leftlist.head.left = root;
map.put(root,new NodeList(leftlist.head,root));
return;
}
NodeList leftlist = map.get(root.left);
NodeList rightlist = map.get(root.right);
leftlist.rear.right = root;
root.left = leftlist.rear;
rightlist.head.left = root;
root.right = rightlist.head;
leftlist.head.left = rightlist.rear;
rightlist.rear.right = leftlist.head;
map.put(root,new NodeList(leftlist.head,rightlist.rear));
return;
}
public void init(Node root, HashMap<Node,NodeList> map)
{
if(root==null)
return;
if(root.left==null && root.right==null)
{
NodeList list = new NodeList(root,root);
map.put(root,list);
return;
}
init(root.left,map);
init(root.right,map);
}
}
这个代码在空间复杂度上还可以优化,可以不用哈希表来保存,递归的过程中直接返回新链表的头尾结点
解法2:中序遍历构造循环链表
解题思路:
因为是二叉搜索树,所以我们中序遍历时是有序递增的,因此我们只要保存两个值
- pre: 前驱结点
- cur: 当前结点
当我们发现pre=null时,说明cur现在处于链表头部
在遍历时我们只要做下面操作即可
cur.left = pre;
pre.rigth = cur;
pre = cur;
这样持续到中序遍历的结束即可
最后只要把头节点的left指向尾结点,尾结点的right指向头节点即可
代码如下:
class Solution {
Node pre, head;
public Node treeToDoublyList(Node root) {
if(root == null) return null;
dfs(root);
head.left = pre;
pre.right = head;
return head;
}
void dfs(Node cur) {
if(cur == null) return;
dfs(cur.left);
if(pre != null) pre.right = cur;
else head = cur;
cur.left = pre;
pre = cur;
dfs(cur.right);
}
}
解法来源
作者:jyd
链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/solution/mian-shi-ti-36-er-cha-sou-suo-shu-yu-shuang-xian-5/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
心得体会
}
解法来源
作者:jyd
链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/solution/mian-shi-ti-36-er-cha-sou-suo-shu-yu-shuang-xian-5/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
心得体会
其实我自己的解法算是效率很低了,但是因为是自己想出来的思路,还是决定将其用代码给实现了
推荐阅读
-
剑指offer37.序列化和反序列化二叉树(详解)
-
剑指 Offer 07. 重建二叉树——【前中序】和【中后序】重建二叉树的递归思路详解
-
剑指offer面试题68 - I. 二叉搜索树的最近公共祖先(python)
-
1601:面试题36. 二叉搜索树与双向链表
-
【剑指offer】_10二叉树和为某一路径值
-
[剑指offer] 二叉搜索树的第k大节点(C++解法)
-
python--剑指offer--简单--68 - I. 二叉搜索树的最近公共祖先
-
剑指offer54.二叉树搜索树的第k大节点
-
剑指offer 面试题63 二叉搜索树的第 k 个结点
-
剑指offer面试题63 二叉搜索树的第k个结点