【Leetcode】109. Convert Sorted List to Binary Search Tree
2024-09-26 17:06:20
Question:
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
Given the sorted linked list: [-10,-3,0,5,9], One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST: 0
/ \
-3 9
/ /
-10 5
Tips:
给定一个有序的单链表,将其转换成一个平衡二叉查找树。
思路:
(1)找到链表的中间位置,作为BST的根节点。方法就是设置两个指针,fast、slow,slow每次走一步,fast每次走两步。当fast先遇到null,slow就指向链表中间节点。
(2)左、右子树的根节点也用相同的方法找到,并作为根节点的左右子树。接下来的结点可用递归来解决。
代码:
public TreeNode sortedListToBST(ListNode head){
if(head==null) return null;
return toBST(head,null);
} private TreeNode toBST(ListNode head,ListNode tail) {
if(head==tail) return null;
ListNode fast=head;
ListNode slow=head;
//循环找到链表中间位置作为根节点。
while(fast!=tail && fast.next!=tail){
slow=slow.next;
fast=fast.next.next;
}
TreeNode root=new TreeNode(slow.val);
root.left=toBST(head,slow);
root.right=toBST(slow.next,tail);
return root;
}
最新文章
- shortcuts on Windows and MacOS
- 其实今天没有欲望..-MySQLi
- 北京程序员 VS 硅谷程序员(转)
- Android学习笔记(第二篇)View中的五大布局
- Escape Sequences
- 标签栏控制器(UITabBarController)
- python笔记1
- Ubuntu 14.04 Android 使用Maven二 创建自己的Mavenproject
- C#- 泛型去除重复项
- Color the ball----HDOJ1556
- 无限循环的ViewPager
- 泛型 ";new的性能";
- C++高效安全的运行时动态类型转换
- android之.9.png详解
- HBase压缩
- 【转】利用apktool反编译apk,并且重新签名打包
- Unicode String to a UTF-8 TypedArray Buffer in JavaScript
- 【从0到1学Web前端】CSS定位问题三(相对定位,绝对定位) 分类: HTML+CSS 2015-05-29 23:01 842人阅读 评论(0) 收藏
- python开发_webbrowser_浏览器控制模块
- Android问题集锦之三十四:android studio导入项目下载gradle-x.x.x-all.zip