資訊專欄INFORMATION COLUMN
摘要：我們可以用和兩個(gè)值來(lái)限定子樹(shù)在鏈表中的位置，通過(guò)遞歸的方式，深入找到最左邊，然后開(kāi)始順序遍歷鏈表鏈表當(dāng)前節(jié)點(diǎn)作為全局變量，這樣無(wú)論遞歸在哪我們都能拿到，同時(shí)建樹(shù)。代碼先遞歸的計(jì)算左子樹(shù)創(chuàng)造根節(jié)點(diǎn)最后遞歸的計(jì)算右子樹(shù)
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.遞歸法 復(fù)雜度
時(shí)間 O(N) 空間 O(H)
思路首先先分析下題目，二叉搜索樹(shù)，有序鏈表，之間有什么關(guān)系？我們知道二叉搜索樹(shù)做深度優(yōu)先搜索就可以從小到大順序讀取樹(shù)中節(jié)點(diǎn)，但是如何從一串有序的數(shù)字還原二叉搜索樹(shù)呢？仔細(xì)觀察的話可以發(fā)現(xiàn)，該串?dāng)?shù)字的中點(diǎn)應(yīng)該就是整棵樹(shù)的根，然后該根節(jié)點(diǎn)的左子樹(shù)的根節(jié)點(diǎn)，又是左半邊的中點(diǎn)，該根節(jié)點(diǎn)的右子樹(shù)的根節(jié)點(diǎn)，又是右半邊的中點(diǎn)，以此往復(fù)，鏈表第一個(gè)節(jié)點(diǎn)，就是最左邊左“子樹(shù)”的根節(jié)點(diǎn)（實(shí)際上已經(jīng)是葉子節(jié)點(diǎn)了，但先看成只有一個(gè)節(jié)點(diǎn)的子樹(shù)，最左邊左子樹(shù)的左節(jié)點(diǎn)和右節(jié)點(diǎn)都是空）。我們可以用start和end兩個(gè)值來(lái)限定子樹(shù)在鏈表中的位置，通過(guò)遞歸的方式，深入找到最左邊，然后開(kāi)始順序遍歷鏈表（鏈表當(dāng)前節(jié)點(diǎn)作為全局變量，這樣無(wú)論遞歸在哪我們都能拿到），同時(shí)建樹(shù)。
代碼public class Solution {
ListNode curr;
public TreeNode sortedListToBST(ListNode head) {
curr = head;
int len = 0;
// 先計(jì)算出鏈表的長(zhǎng)度
while(head != null){
head = head.next;
len++;
}
curr = head;
// 開(kāi)始建樹(shù)
return buildTree(0, len - 1);
}
private TreeNode buildTree(int start, int end){
// 如果start>end，說(shuō)明子樹(shù)已經(jīng)小到?jīng)]有節(jié)點(diǎn)了，直接返回null
if(start > end){
return null;
}
// 找到中點(diǎn)
int mid = start + (end - start) / 2;
// 先遞歸的計(jì)算左子樹(shù)
TreeNode left = buildTree(start, mid - 1);
// 然后建立根節(jié)點(diǎn)
TreeNode root = new TreeNode(curr.val);
// 鏈表順序遍歷
curr = curr.next;
// 最后計(jì)算右子樹(shù)
TreeNode right = buildTree(mid + 1, end);
// 將三個(gè)節(jié)點(diǎn)連接起來(lái)
root.left = left;
root.right = right;
return root;
}
}
2018/10
var curr *ListNode
func buildTree(start int, end int) *TreeNode {
if start > end {
return nil
}
mid := start + (end-start)/2
root := &TreeNode{}
root.Left = buildTree(start, mid-1)
root.Val = curr.Val
curr = curr.Next
root.Right = buildTree(mid+1, end)
return root
}
func sortedListToBST(head *ListNode) *TreeNode {
length := 0
curr = head
for curr != nil {
curr = curr.Next
length++
}
curr = head
return buildTree(0, length-1)
}
Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.遞歸法 復(fù)雜度
時(shí)間 O(N) 空間 O(H)
思路和用鏈表建樹(shù)的思路相似，實(shí)現(xiàn)更加簡(jiǎn)單，因?yàn)閿?shù)組支持隨機(jī)查詢，我們可以直接訪問(wèn)中點(diǎn)而無(wú)須遍歷鏈表。
代碼public class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return buildTree(nums, 0, nums.length - 1);
}
private TreeNode buildTree(int[] nums, int start, int end){
if(start > end){
return null;
}
int mid = start + (end - start) / 2;
// 先遞歸的計(jì)算左子樹(shù)
TreeNode left = buildTree(nums, start, mid - 1);
// 創(chuàng)造根節(jié)點(diǎn)
TreeNode root = new TreeNode(nums[mid]);
// 最后遞歸的計(jì)算右子樹(shù)
TreeNode right = buildTree(nums, mid + 1, end);
root.left = left;
root.right = right;
return root;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64624.html
摘要：解題思路平衡二叉樹(shù)，其實(shí)就是數(shù)組中間的數(shù)作為根，利用遞歸實(shí)現(xiàn)左子樹(shù)和右子樹(shù)的構(gòu)造。 Convert Sorted Array to Binary Search TreeGiven an array where elements are sorted in ascending order, convert it to a height balanced BST. 1.解題思路平衡二叉樹(shù)，...
摘要：二分法找到數(shù)組的中位數(shù)，置為樹(shù)的，遞歸找到前半段和后半段的中位數(shù)，分別置為左右子樹(shù)。 Problem Given a sorted (increasing order) array, Convert it to create a binary tree with minimal height. Example Given [1,2,3,4,5,6,7], return 4 ...
摘要：思路根據(jù)的性質(zhì)，問(wèn)題轉(zhuǎn)化為找一個(gè)里的中位數(shù)，用一個(gè)函數(shù)，一路找中點(diǎn)，再通過(guò)前序遍歷的方法把起來(lái)代碼 Convert Sorted Array to Binary Search Tree With Minimal Height Given a sorted (increasing order) array, Convert it to create a binarytree with m...
Problem 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 whi...
摘要：題目要求給一個(gè)按照遞增順序排列的鏈表。將該鏈表轉(zhuǎn)化為平衡二叉樹(shù)。思路和代碼在這里需要注意的是，因?yàn)樘峁┑臄?shù)據(jù)結(jié)構(gòu)為鏈表，所以我們必須順序遍歷才能知道該鏈表的長(zhǎng)度以及該鏈表的中間位置。并依次遞歸左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。 題目要求 Given a singly linked list where elements are sorted in ascending order, convert i...
閱讀 2286·2021-11-23 09:51
閱讀 5681·2021-09-22 15:39
閱讀 3355·2021-09-02 15:15
閱讀 3506·2019-08-30 15:54
閱讀 2364·2019-08-30 15:53
閱讀 1404·2019-08-30 14:04
閱讀 2459·2019-08-29 18:33
閱讀 2378·2019-08-29 13:08
