题目描述
- LintCode 1534 · Convert Binary Search Tree to Sorted Doubly Linked List
- 牛客网 JZ36 二叉搜索树与双向链表
- LeetCode LCR 155. 将二叉搜索树转化为排序的双向链表
样例
输入
[10, 6, 14, 4, 8, 12, 16, null, null, null, null, null, null, null, null]
输出
head to tail:[4, 6, 8, 10, 12, 14, 16]
tail to head:[16, 14, 12, 10, 8, 6, 4]
算法1
Morris遍历(原始版)
时间复杂度
:$O(NlogN)$
空间复杂度
:$O(1)$
算法过程:
1. 先用Morris遍历算法
遍历一遍二叉树,注意,在遍历过程中,如果重新遍历之前遍历过的节点,我们不恢复指针。(即morris函数中被注释掉的predecessor.right = null;
)。
2. 再从头遍历一遍。遍历过程中,(情况1)若节点的右指针指向祖先节点,那么直接跳过,因为它已经正确地指向了当前节点的后继节点;(情况2)若节点的右指针指向右儿子节点,那么我们需要将当前节点的右指针调整为指向当前节点的后继节点。我们用cur != getPredecessor(cur.right)
来判断当前指针的右指针是指向祖先节点还是右儿子节点。若为情况1,那么将遍历cur.right.left
节点的右子树一遍,且结果为当前节点cur
;若为情况2,则会遍历一遍cur.right
的左子树的最右侧path(即从cur.right.left
节点至叶子节点)上的节点一遍。第一种情况的计算量加起来为$O(NlogN)$级别,这可以通过计算最坏情况得出,最坏情况就是整棵树为满二叉树,把所有节点的左儿子的右子树的size
累加起来即可:
$$ \sum_{i=0}^{h-2} 2^i * (2^{h-2-i} - 1)$$
$\quad$然后,根据满二叉树的性质,又有$N=2^h - 1$,整理后即可得出结果的量级为$O(NlogN)$级别。对于第二种情况,遍历的节点数量加起来不超过$N$。
$\quad$最后,我们再加上每个节点都遍历了一次,时间复杂度为:$O(NlogN+N+N)=O(NlogN)$
参考文献
Java 代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode convert(TreeNode root) {
if (root == null) {
return null;
}
TreeNode head = root;
while (head.left != null) {
head = head.left;
}
morris(root);
TreeNode cur = head;
while (cur.right != null) {
if (cur != getPredecessor(cur.right)) {
// get successor node of the cur node
TreeNode successor = getSuccessor(cur);
cur.right = successor;
}
cur.right.left = cur;
cur = cur.right;
}
// needed when convert a BST to a sorted circular doubly-linked list
// cur.right = head;
// head.left = cur;
return head;
}
void morris(TreeNode root) {
TreeNode cur = root;
while (cur != null) {
if (cur.left != null) {
// get predecessor node of cur node
TreeNode predecessor = getPredecessor(cur);
if (predecessor.right == null) {
predecessor.right = cur;
cur = cur.left;
continue;
}
// predecessor.right = null;
}
cur = cur.right;
}
}
TreeNode getSuccessor(TreeNode root) {
assert root != null;
TreeNode p = root.right;
while (p != null && p.left != null && p.left != root) {
p = p.left;
}
return p;
}
TreeNode getPredecessor(TreeNode root) {
assert root != null;
TreeNode p = root.left;
while (p != null && p.right != null && p.right != root) {
p = p.right;
}
return p;
}
}
算法2
Morris遍历(优化版) (仅适用于节点值唯一的场景)
时间复杂度
: $O(N)$
空间复杂度
:$O(1)$
$\quad$算法1里的瓶颈在于判断一个节点的右指针究竟是指向祖先节点还是指向右儿子节点,这个我们可以利用二叉搜索树的性质来在$O(1)$的时间内判断出来。因为如果当前节点cur
的右指针指向的是祖先节点,那么一定有cur.right.left != null && cur.right.left.val <= cur.val
。
参考文献
Java 代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode convert(TreeNode root) {
if (root == null) {
return null;
}
TreeNode head = root;
while (head.left != null) {
head = head.left;
}
morris(root);
TreeNode cur = head;
while (cur.right != null) {
if (cur.right.left == null || cur.right.left.val > cur.val) {
// get successor node of the cur node
TreeNode successor = getSuccessor(cur);
cur.right = successor;
}
cur.right.left = cur;
cur = cur.right;
}
// needed when convert a BST to a sorted circular doubly-linked list
// cur.right = head;
// head.left = cur;
return head;
}
void morris(TreeNode root) {
TreeNode cur = root;
while (cur != null) {
if (cur.left != null) {
// get predecessor node of cur node
TreeNode predecessor = getPredecessor(cur);
if (predecessor.right == null) {
predecessor.right = cur;
cur = cur.left;
continue;
}
// predecessor.right = null;
}
cur = cur.right;
}
}
TreeNode getSuccessor(TreeNode root) {
assert root != null;
TreeNode p = root.right;
while (p != null && p.left != null && p.left != root) {
p = p.left;
}
return p;
}
TreeNode getPredecessor(TreeNode root) {
assert root != null;
TreeNode p = root.left;
while (p != null && p.right != null && p.right != root) {
p = p.right;
}
return p;
}
}
算法3. Morris中序遍历
时间复杂度
: $O(N)$
空间复杂度
: $O(1)$
参考文献
Java代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
TreeNode head = null, tail = null;
public TreeNode convert(TreeNode root) {
if(root == null){
return root;
}
morris(root);
TreeNode p = head;
while(p.right != null){
p.right.left = p;
p = p.right;
}
// needed when convert a BST to a sorted circular doubly-linked list
// head.left = tail;
// tail.right = head;
return head;
}
void morris(TreeNode root) {
TreeNode cur = root;
while (cur != null) {
if(cur.left == null){
if(head == null){
head = tail = cur;
}
else{
tail.right = cur;
tail = tail.right;
}
cur = cur.right;
}
else {
// get predecessor node of cur node
TreeNode predecessor = getPredecessor(cur);
if (predecessor.right == null) {
predecessor.right = cur;
cur = cur.left;
}
else{
// predecessor.right = null;
tail.right = cur;
tail = tail.right;
cur = cur.right;
}
}
}
}
TreeNode getSuccessor(TreeNode root) {
assert root != null;
TreeNode p = root.right;
while (p != null && p.left != null && p.left != root) {
p = p.left;
}
return p;
}
TreeNode getPredecessor(TreeNode root) {
assert root != null;
TreeNode p = root.left;
while (p != null && p.right != null && p.right != root) {
p = p.right;
}
return p;
}
}