欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-07-04 18:37:37
我的LeetCode:https://leetcode cn.com/u/ituring/ 我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii LeetCode 面试题36. 二叉搜索树与双向链表 题目 输入一棵二叉搜索树, ......

我的leetcode:

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

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

题目

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

为了让您更好地理解问题,以下面的二叉搜索树为例:
LeetCode 面试题36. 二叉搜索树与双向链表

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

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

__注意:__本题与主站 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);
	}
}