LeetCode <dfs>108&109. Array & List to Binary Search Tree
原创LeetCode <dfs>108&109. Array & List to Binary Search Tree
原创
108.Convert Sorted Array to Binary Search Tree
Given an array 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 array: [-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题目大意:把一个有序的数组转化为二分搜索树
解法：
思路：把中间的元素作为根节点，构造二分搜索树。
public TreeNode sortedArrayToBST(int[] nums) {
int length = nums.length;
sortedArrayToBST_recursion(0,length-1,nums);
return sortedArrayToBST_recursion(0,length-1,nums);
}
public TreeNode sortedArrayToBST_recursion(int start , int end ,int[] nums){
if(start>end) return null;
int mid = (end + start)/2;
TreeNode node = new TreeNode(nums[mid]);
node.left = sortedArrayToBST_recursion(start,mid-1,nums);
node.right = sortedArrayToBST_recursion(mid+1,end,nums);
return node;
}109.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.
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题目大意：把一个有序的链表转化为二分搜索树。
解法：
public TreeNode sortedListToBST(ListNode head) {
if (head == null) return null;
ListNode fast = head;
ListNode slow = head;
ListNode pre = null;
while (fast!=null && fast.next !=null){
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
if (pre!=null) pre.next =null;
else head = null;
TreeNode root = new TreeNode(slow.val);
ListNode start = head;
root.left = sortedListToBST(start);
start = slow.next;
root.right = sortedListToBST(start);
return root;
}换一种写法：思路与上面同
public TreeNode sortedListToBST(ListNode head) {
if (head == null) return null;
ListNode fast = head;
ListNode slow = head;
ListNode pre = new ListNode(0);
pre.next = head;
while (fast!=null && fast.next !=null){
pre = pre.next;
slow = slow.next;
fast = fast.next.next;
}
if (pre.next == head) head =null;
pre.next = null;
TreeNode root = new TreeNode(slow.val);
ListNode start = head;
root.left = sortedListToBST(start);
start = slow.next;
root.right = sortedListToBST(start);
return root;
}
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。