问题描述:
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
原问题链接:https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
问题分析
这个问题和前面的问题有点不一样,它的输入不是一个array,而是一个链表。那么,这个时候如果还是按照前面一个个遍历过去找位置然后设置节点的话,效率会很低。因此需要做一些调整。
方法一:
我们比较基于链表和基于数组的实现,前面基于数组的实现是需要根据当前节点所在的位置来定义根节点以及相对的左右子树。而链表的输入问题根源在于如果要找到一个元素所在的位置以及对应的元素值效率太低了。只要有办法找到这个就可以很快。
那么,我们可以用一个Map<Integer, ListNode>来保存在链表里每个元素的位置和它所对应的元素。然后再利用和前面基于数组同样的思路来递归构造平衡二叉搜索树。
详细的代码实现如下:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { private Map<Integer, ListNode> map = new HashMap<>(); public TreeNode sortedListToBST(ListNode head) { if(head == null) return null; int count = 0; ListNode node = head; while(node != null) { map.put(count, node); count++; node = node.next; } return sortedListToBST(map, 0, count - 1); } private TreeNode sortedListToBST(Map<Integer, ListNode> map, int l, int r) { if(l > r) return null; int mid = l + (r - l) / 2; TreeNode node = new TreeNode(map.get(mid).val); node.left = sortedListToBST(map, l, mid - 1); node.right = sortedListToBST(map, mid + 1, r); return node; } }
这里的实现用Map保存了元素位置和元素值之间的映射,提升了查找元素的效率。但是整体的效率仍然一般,因为这里有一个从int到Integer元素的boxing和unboxing转换。
那么,除了上述的方法,还有没有其他的方法呢?
方法二
上面的那个办法也算是一个不错的思路了。不过这里还有一个办法更加巧妙。因为对于一个排序后的链表来说,它就相当于是对二叉树的中序遍历得到的结果。如果我们模拟一个二叉树中序遍历里递归调用回溯的过程,就可以一边遍历二叉树一边把对应的二叉树给建立起来。
比如说这里链表的第一个节点,它正好就对应二叉树的最左下角的元素。而它的下一个元素呢,正好就对应着前面二叉树递归调用里要回溯到的那个节点。于是我们可以有如下的代码实现:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; next = null; } * } */ /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { private ListNode cur; public TreeNode sortedListToBST(ListNode head) { cur = head; return generate(count(head)); } private TreeNode generate(int n) { if(n == 0) return null; TreeNode node = new TreeNode(0); node.left = generate(n / 2); node.val = cur.val; cur = cur.next; node.right = generate(n - n / 2 - 1); return node; } private int count(ListNode node) { int count = 0; while(node != null) { count++; node = node.next; } return count; } }
这种方法比较巧妙的糅合了二叉树中序遍历以及链表递进的关系,值得仔细揣摩。
相关推荐
lru缓存leetcode leetcode 大批 41. First Missing Positive 广度优先搜索 773. Sliding Puzzle 864. Shortest Path to Get All Keys 深度优先搜索 996. Number of Squareful Arrays 拓扑排序 269. Alien Dictionary...
leetcode的题目:Balanced Binary Tree
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode卡 leetcode exercises 3-5 solutions everyday. fighting~ TODO array Best Time to Buy and Sell Stock II Valid Sudoku linked list Palindrome linked list Linked List Cycle trees Convert Sorted ...
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
LeetCode::laptop:LeetCode解决方案
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
leetcode添加元素使和等于 LeetCode leetcode 指针类型题目 1. 链表 函数参数传入的链表都没有链表的头,从第一个有数据的节点开始 函数返回一个链表,这个链表也没有头 2. 内存分配 二维数组内存分配 二维数组分配...
to Integer 11 Container with Most Water 14 Longest Common Prefix 15 Three Sum 16 Three Sum Closest 20 Valid Parentheses 26 Remove Duplicates from Sorted Array 48 Rotate Image 53 Maximum Subarray 55 ...
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
leetcode题目:Best Time to Buy and Sell Stock II
LeetCode Merge 2 Sorted Lists解决方案
leetcode lintcode差异 Lintcode 解题思路记录 Table of Contents Linked List Convert Sorted List to Binary Search Tree Given a singly linked list where elements are sorted in ascending order, convert it ...
Leetcode:Leetcode提交
LeetCode 101:和你一起你轻松刷题(C++)
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
leetcode LeetCode刷题 题号是LeetCode原题,题目是自己的解答 Easy 题号 题目 Tags Star Company HashMap :star: :star: :star: Integer :star: :star: String :star: String、Stack :star: :star: :star: ...
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表