- 浏览: 136953 次
文章分类
- 全部博客 (189)
- Tree (14)
- Dynamic Programming (34)
- Array (20)
- Search (1)
- Hash (12)
- Backtracking (22)
- Divide and Conque (8)
- Greedy (6)
- Stack (12)
- software (0)
- List (7)
- Math (22)
- Two pointers (16)
- String (20)
- Linux (1)
- Sliding Window (4)
- Finite State Machine (1)
- Breadth-first Search (7)
- Graph (4)
- DFS (6)
- BFS (3)
- Sort (9)
- 基础概念 (2)
- 沟通表达 (0)
- Heap (2)
- Binary Search (15)
- 小结 (1)
- Bit Manipulation (8)
- Union Find (4)
- Topological Sort (1)
- PriorityQueue (1)
- Design Pattern (1)
- Design (1)
- Iterator (1)
- Queue (1)
最新评论
-
likesky3:
看了数据结构书得知并不是迭代和递归的区别,yb君的写法的效果是 ...
Leetcode - Graph Valid Tree -
likesky3:
迭代和递归的区别吧~
Leetcode - Graph Valid Tree -
qb_2008:
还有一种find写法:int find(int p) { i ...
Leetcode - Graph Valid Tree -
qb_2008:
要看懂这些技巧的代码确实比较困难。我是这么看懂的:1. 明白这 ...
Leetcode - Single Num II -
qb_2008:
public int singleNumber2(int[] ...
Leetcode - Single Num II
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
[分析]
思路1复杂度是O(nlogn),实现过程中发现自己二指针法一开始是写错的,错误的结果是二分后左边会比右边多两个元素,在Reorder List中这种写法之所以也能被Accept完全是凑巧,因为多两个不影响结果~
思路2:参考https://leetcode.com/discuss/23676/share-my-o-1-space-and-o-n-time-java-code 相比于Convert Sorted Array to Binary Search Tree难点是不能常数时间内找到链表的中间节点,此题有助于加深对中序遍历的理解。
[分析]
思路1复杂度是O(nlogn),实现过程中发现自己二指针法一开始是写错的,错误的结果是二分后左边会比右边多两个元素,在Reorder List中这种写法之所以也能被Accept完全是凑巧,因为多两个不影响结果~
思路2:参考https://leetcode.com/discuss/23676/share-my-o-1-space-and-o-n-time-java-code 相比于Convert Sorted Array to Binary Search Tree难点是不能常数时间内找到链表的中间节点,此题有助于加深对中序遍历的理解。
public class Solution { // Method 2: O(N) private ListNode curr; public TreeNode sortedListToBST(ListNode head) { if (head == null) return null; int n = 0; ListNode p = head; while (p != null) { n++; p = p.next; } curr = head; return inorder(1, n); } public TreeNode inorder(int l, int r) { if (l > r) return null; int mid = l + (r - l) / 2; TreeNode left = inorder(l, mid - 1); TreeNode root = new TreeNode(curr.val); root.left = left; curr = curr.next; root.right = inorder(mid + 1, r); return root; } // Method 1: O(NlogN) public TreeNode sortedListToBST1(ListNode head) { if (head == null) return null; if (head.next == null) return new TreeNode(head.val); ListNode dummy = new ListNode(0); dummy.next = head; ListNode slow = dummy, fast = head; while (fast.next != null) { fast = fast.next; if (fast.next != null) { slow = slow.next; fast = fast.next; } } ListNode mid = slow.next; TreeNode root = new TreeNode(mid.val); root.right = sortedListToBST(mid.next); if (mid != head) { slow.next = null; root.left = sortedListToBST(head); } return root; } }
发表评论
-
Inorder Successor in BST
2015-09-26 17:49 718[分析] 参考https://leetcode.com/dis ... -
Lowest Common Ancestor of A Binary Tree
2015-09-26 11:39 567[分析] 最近公共祖先(LCA)是一个经典问题,以前没有好好 ... -
Leetcode - Closest Binary Search Tree Value II
2015-09-13 14:16 785[分析] 思路1:遍历所有节点找到和 target最接近的 k ... -
Leetcode - LRU Cache
2015-09-03 18:31 538[分析] 自己使用HashMap + LinkedList/A ... -
Leetcode - Graph Valid Tree
2015-09-02 08:50 2269Given n nodes labeled from 0 to ... -
Leetcode - Closest Binary Search Tree Value II
2015-09-01 09:50 3179Given a non-empty binary search ... -
Leetcode - Binary Tree Upside Down
2015-08-29 18:50 411Given a binary tree where all t ... -
Leetcode - Verify Preorder Sequence in Binary Search Tree
2015-08-29 16:46 3028[分析] 思路1:暴力法,遍历当前待检查数组,找到第一个大于数 ... -
Leetcode - Insertion Sort List
2015-08-15 19:27 653Sort a linked list using insert ... -
Leetcode - Kth Smallest Element in BST
2015-08-11 10:26 656[分析] 思路1: 递归中序遍历,返回中序遍历中的第k个数。 ... -
Leetcode - Palindrome Linked List
2015-07-12 08:23 517Given a singly linked list, det ... -
Leetcode - Merge k Sorted Lists
2015-07-08 09:57 460Merge k sorted linked lists and ... -
Leetcode - Recover Binary Search Tree
2015-07-02 09:27 525Two elements of a binary search ... -
Leetcode - Validate Binary Search Tree
2015-07-01 08:31 593Given a binary tree, determine ... -
Leetcode - Count Complete Tree Nodes
2015-06-07 20:51 770Definition of a complete binary ... -
Leetcode - Contains Duplicate III
2015-06-07 20:08 506Given an array of integers, fi ... -
Leetcode - Reversed Linked ListII
2015-05-19 22:19 517Reverse a linked list from pos ... -
Leetcode - Reversed Linked List
2015-05-19 22:14 551Reverse a singly linked list. ... -
MockInterview-FindNextValue
2015-04-12 08:57 0[题目] Return the next elemen ... -
MockInterview-Implement Dictionary
2015-04-12 08:56 0[题目] Implement a dictionary, s ...
相关推荐
python python_leetcode_109_Convert_Sorted_List_to_Binary_Search_Tree
java java_leetcode-114-flatten-binary-tree-to-linked-list
《在IDE中高效进行LeetCode练习:leetcode-editor的深度解析》 在编程学习与技能提升的过程中,LeetCode作为一款广受欢迎的在线编程挑战平台,帮助众多开发者锻炼算法思维,提高编程能力。而为了进一步提升练习体验...
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
leetcode-习题集资源leetcode-习题集资源leetcode-习题集资源leetcode-习题集资源leetcode-习题集资源leetcode-习题集资源
在IDE中解决LeetCode问题,支持leetcode.com与leetcode-cn.com,满足基本的做题需求。 理论上支持: IntelliJ IDEA PhpStorm WebStorm PyCharm RubyMine AppCode CLion GoLand DataGrip Rider MPS Android Studio。
LeetCode Editor 7.4 版本的下载是一个名为 "leetcode-editor" 的压缩包文件。这个压缩包的导入过程非常简单,只需要将它直接拖入 IDEA 界面,IDEA 会自动识别并安装插件。这种方式使得安装过程无需额外的步骤,对于...
leetcode-习题集资源源代码leetcode-习题集资源源代码leetcode-习题集资源源代码leetcode-习题集资源源代码leetcode-习题集资源源代码
~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/vsc-leetcode-cli/bin/leetcode /usr/local/bin/leetcode 修改模板 open ~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/...
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
javascript js_leetcode题解之109-convert-sorted-list-to-binary-search-tree.js
`swift-Swif-LeetCode-Utils` 是一个实用工具库,它为Swift程序员提供了方便快捷的方法来处理这些问题。这个项目可以帮助你更高效地进行LeetCode上的编程练习,提升你的解决方案的可读性和简洁性。 首先,让我们...
java java_leetcode-115-distinct-subsquences
java java_leetcode-112-path-sum
java java_leetcode-101-symmetric-tree
java java_leetcode-100-same-tree
java java_leetcode-110-balanced-binary-tree
java java_leetcode-73-set-matrix-zeroes