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

2020-05-12 16:04:16来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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

我的LeetCode:https://leetcode-cn.com/u/ituring/

我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii

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

题目

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

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

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

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

__注意:__本题与主站 426 题相同:https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

思路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);
	}
}

原文链接:https://www.cnblogs.com/izhoujie/p/12876289.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:SpringBoot中ConditionalOnClass注解的原理

下一篇:在培训机构花了好几万学Java,当了程序员还常被鄙视,这是招谁惹