【LeetCode109-20.8.18-有序链表转二叉搜索树】题目链接：LeetCode109
过程：一开始想直接写二叉搜索树，一个节点一个节点的插入树中，但感觉好麻烦而且不会。索性去看题解。（我太呆了 ）题解真好。
做法：分治，评论里有位bfs建树,dfs中序遍历填值感觉可以。
代码：
/**
* Definition for singly-linked list.
* public class ListNode {
*int val;
*ListNode next;
*ListNode() {}
*ListNode(int val) { this.val = val;
}
*ListNode(int val, ListNode next) { this.val = val;
this.next = next;
}
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
*int val;
*TreeNode left;
*TreeNode right;
*TreeNode() {}
*TreeNode(int val) { this.val = val;
}
*TreeNode(int val, TreeNode left, TreeNode right) {
*this.val = val;
*this.left = left;
*this.right = right;
*}
* }
*/class Solution {
ListNode globalNode;
public TreeNode sortedListToBST(ListNode head) {
int len=0;
for(ListNode node=head;
node!=null;
node=node.next)len++;
globalNode=head;
return buildTree(0,len-1);
}
public TreeNode buildTree(int left,int right){
if(left>right)return null;
int mid=(left+right+1)/2;
TreeNode node=new TreeNode();
node.left=buildTree(left,mid-1);
node.val=globalNode.val;
globalNode=globalNode.next;
node.right=buildTree(mid+1,right);
return node;
}}
推荐阅读
- LeetCode-20.8.22-24点游戏
- LeetCode-2020.8.20-扫雷游戏
- LeetCode647-20.8.19-回文字串
- LeetCode111-20.8.21-二叉树的最小深度