新博文地址:[leetcode]Convert Sorted List to Binary Search Tree
Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
跟这道题很相似,没道理没写博文啊(= =//)算了,反正也简单,道理也一样,简单说一下吧。
这道题要求高度balance,因此可以考虑采取二分法,每次找到链表的中点,左边的一半生成左子树,右边的是右子树,这样就能够达到平衡了。但是链表如何能找到中点呢?顺序查找肯定啦。
但是不知道大家对快慢指针是否熟悉:
找中间节点
快指针每次走两步,慢指针每次走一步,当快指针走到头,慢指针刚好走到一半,当然有一些边界情况需要考虑,比如链表就一个节点的情况等等。
找到了中间节点之后呢?
前面说了左边一半是左子树,右边是右子树。因此我们要根据中间节点将原链表分裂,因此我们还需要找到中间节点的前驱节点preMid,并将preMid.next = null,这样head就代表了左子树,mid.next 就是右子树,递归。
代码如下:
public TreeNode sortedListToBST(ListNode head) { if(head == null){ return null; } ListNode mid = getMidNode(head); ListNode preMid = head; if(mid != head){//找mid的前驱节点 while(preMid.next != mid){ preMid = preMid.next; } }else{ head = null;//当mid就是head节点时,即表示左子树为空了 } preMid.next = null;//截断之后,head 表示左子树 ListNode rightHead = mid.next; TreeNode root = new TreeNode(mid.val); root.left = sortedListToBST(head); root.right = sortedListToBST(rightHead); return root; } private ListNode getMidNode(ListNode head){ if(head == null){ return null; } ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null){ try{ fast = fast.next.next; }catch(NullPointerException e){ return slow; } slow = slow.next; } return slow; }
相关推荐
leetcode的题目:Balanced Binary Tree
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卡leetcode 二叉树卡片 LeetCode 二叉树卡片问题的章节智解
Convert Sorted List to Binary Search Tree LCA of BST Kth Smallest Element in a BST 二叉树的递归 Minimum Depth of Binary Tree Maximum Depth of Binary Tree Path Sum Path Sum II Binary Tree Maximum Path ...
* [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...
leetcode 不会二叉树倾斜 给定一棵二叉树,返回整棵树的倾斜度。 树节点的倾斜度定义为所有左子树节点值的总和与所有右子树节点值的总和之间的绝对差。 空节点的倾斜度为 0。 整棵树的倾斜度定义为所有节点倾斜度的...
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_practices_learncard_binarytree 我的 leetcode 练习二叉树学习卡在 100% 完成 :) 我的 Java8 备忘单:
leetcode卡除非您已经使用过卡片,否则不要看这里。 做真实的自己!
leetcode 不会LeetCode_563--二叉树倾斜 给定一棵二叉树,返回整棵树的倾斜度。 树节点的倾斜度定义为所有左子树节点值的总和与所有右子树节点值的总和之间的绝对差。 空节点的倾斜度为 0。 整棵树的倾斜度定义为...
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 Merge 2 Sorted Lists解决方案
BinaryTree.py是一个方便的工具,它可以构建和显示编码时所需的二叉树 演示 您需要在使用之前导入该类 import BinaryTree as bt 从值/对象列表或二叉树构造二叉树 t1 = bt.BinaryTree([1,2,3,4,5,'#',6,7,'#','#','#...
编程问题 , , 等问题的Java解决方案。每个问题都附带说明和解决方案。法昂包含FAANG(Facebook,Amazon,Apple,Netflix和Google)公司用于采访的编程问题。 至少那是互联网所说的... 此软件包中不仅存在FAANG问题...
704.Binary_Search二分查找【LeetCode单题讲解系列】
Programming Questions on BinarySearch, LeetCode, CodeChef
二分查找Binary_Search套路和解题模板【LeetCode刷题套路教程3】
leetcode 数据结构题目中的答案,已经调试,直接运行,求二叉树的最小深度
leetcode伪代码convert-binary-number-in-a-linked-list-to-integer 题目解读: 题目来源: 原文: Given head which is a reference node to a singly-linked list. The value of each node in the linked list is ...
144.Binary_Tree_Preorder_Traversal二叉树的前序遍历【LeetCode单题讲解系列】