LeetCode 面试题36. 二叉搜索树与双向链表

我的leetcode：

我的leetcode刷题源码[github]：https://github.com/izhoujie/algorithmcii

leetcode 面试题36. 二叉搜索树与双向链表

题目

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

为了让您更好地理解问题，以下面的二叉搜索树为例：

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

__注意：__本题与主站 426 题相同：

来源：力扣（leetcode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

思路1-中序遍历然后拼接

中序遍历搜索二叉树可得到排序节点，然后把节点顺序拼接为双向链表即可；

算法复杂度:

• 时间复杂度： $ {\color{magenta}{\omicron\left(n\right)}} $
• 空间复杂度： $ {\color{magenta}{\omicron\left(n\right)}} $ 保存节点的list空间

思路2-中序遍历时就地完成链表转换

在中序遍历时就完成到链表的转换，中间节点的指向操作比较绕，需要仔细分析；
未使用额外空间；

算法复杂度:

• 时间复杂度： $ {\color{magenta}{\omicron\left(n\right)}} $
• 空间复杂度： $ {\color{magenta}{\omicron\left(1\right)}} $

算法源码示例

package leetcode;

import java.util.arraylist;
import java.util.list;

/**
 * @author zhoujie
 * @date 2020年3月14日 下午6:10:03 
 * @description: 面试题36. 二叉搜索树与双向链表
 *
 */
public class leetcode_offer_36 {

}

//definition for a node.
class node_offer_36 {
	public int val;
	public node_offer_36 left;
	public node_offer_36 right;

	public node_offer_36() {
	}

	public node_offer_36(int _val) {
		val = _val;
	}

	public node_offer_36(int _val, node_offer_36 _left, node_offer_36 _right) {
		val = _val;
		left = _left;
		right = _right;
	}
};

class solution_offer_36 {
	/**
	 * @author: zhoujie
	 * @date: 2020年3月14日 下午7:04:20 
	 * @param: @param root
	 * @param: @return
	 * @return: node_offer_36
	 * @description: 1-先用list对搜索二叉树顺次保存，然后遍历list组装链表；
	 *
	 */
	public node_offer_36 treetodoublylist_1(node_offer_36 root) {
		if (root == null) {
			return root;
		}
		list<node_offer_36> list = new arraylist<node_offer_36>();
		aftertree(root, list);
		for (int i = 1; i < list.size(); i++) {
			node_offer_36 node1 = list.get(i - 1);
			node_offer_36 node2 = list.get(i);
			node1.right = node2;
			node2.left = node1;
		}
		node_offer_36 node1 = list.get(0);
		node_offer_36 node2 = list.get(list.size() - 1);
		node1.left = node2;
		node2.right = node1;
		return list.get(0);
	}

	/**
	 * @author: zhoujie
	 * @date: 2020年5月12日 下午2:49:49 
	 * @param: @param root
	 * @param: @param list
	 * @return: void
	 * @description: 中序遍历搜索二叉树得到排序list；
	 *
	 */
	private void aftertree(node_offer_36 root, list<node_offer_36> list) {
		if (root == null) {
			return;
		}
		aftertree(root.right, list);
		list.add(0, root);
		aftertree(root.left, list);
	}

	/**
	 * @author: zhoujie
	 * @date: 2020年3月14日 下午7:14:31 
	 * @param: @param root
	 * @param: @return
	 * @return: node_offer_36
	 * @description: 2-直接在遍历链表时完成前继指针和后继指针的变换；（还没看太明白）
	 *
	 */
	node_offer_36 pre, head, tail;

	public node_offer_36 treetodoublylist_2(node_offer_36 root) {
		if (root == null) {
			return root;
		}
		transform(root);
		head.left = tail;
		tail.right = head;
		return head;
	}

	private void transform(node_offer_36 root) {
		if (root == null) {
			return;
		}
		transform(root.left);
		root.left = pre;
		if (pre == null) {
			head = root;
		} else {
			pre.right = root;
		}
		pre = root;
		tail = root;
		transform(root.right);
	}
}