萬(wàn)卷古今消永日，一窗昏曉送流年
【白話譯文】
在萬(wàn)卷書(shū)中消磨自己整整的一天，南窗下讓自己生命的河流靜靜地流過(guò)
正文
今天我們介紹如何將一個(gè)有序數(shù)組轉(zhuǎn)換為平衡二叉搜索樹(shù)
首先我們介紹一下什么是二叉搜索樹(shù)，二叉搜索樹(shù)是一種始終滿(mǎn)足左子樹(shù)小于根，根小于右子樹(shù)的特性的二叉樹(shù)，那么平衡二叉樹(shù)就是 任意節(jié)點(diǎn)的子樹(shù)的高度差的絕對(duì)值都小于等于1。
大家理解了什么是平衡二叉搜索樹(shù)應(yīng)該就會(huì)感覺(jué)到這題非常的簡(jiǎn)單装获，因?yàn)檫@個(gè)樹(shù)中序遍歷之后就是一個(gè)有序的數(shù)組。所以我們只需要一直找到數(shù)組的中間點(diǎn)厉颤，每次將數(shù)組左邊的值放到左子樹(shù)穴豫，數(shù)組右邊的值放到右子樹(shù)就能實(shí)現(xiàn)這一操作了。
使用二分法實(shí)現(xiàn)，上代碼
public static void main(String[] args) {
int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8};
System.out.println(sortedArrayToBST(arr));
}
public static TreeNode sortedArrayToBST(int[] nums) {
return helper(nums, 0, nums.length - 1);
}
public static TreeNode helper(int[] nums, int left, int right) {
if (left > right) {
return null;
}
// 總是選擇中間位置左邊的數(shù)字作為根節(jié)點(diǎn)
int mid = (left + right) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, left, mid - 1);
root.right = helper(nums, mid + 1, right);
return root;
}
遞歸就是不停的回溯精肃，由于比較簡(jiǎn)單秤涩，實(shí)在不知道講什么，我就把遞歸的回溯過(guò)程寫(xiě)出來(lái)吧
本篇文章已經(jīng)結(jié)束司抱，下面是記錄遞歸的運(yùn)行過(guò)程
//第一次進(jìn)入 left = 0, right = 8
if (left > right) {
return null;
}
int mid = (left + right) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, left, mid - 1);
root.right = helper(nums, mid + 1, right);
//第一次進(jìn)入 left = 0, right = 8
if (left > right) {
return null;
}
//mid = 4
int mid = (left + right) / 2;
//nums[mid] = 4
TreeNode root = new TreeNode(nums[mid]);
root.left =
//遞歸回溯進(jìn)入 left = 0, right = 3
if (left > right) {
return null;
}
//mid = 1
int mid = (left + right) / 2;
//nums[mid] = 1
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, left, mid - 1);
root.right = helper(nums, mid + 1, right);
root.right = helper(nums, mid + 1, right);
//第一次進(jìn)入 left = 0, right = 8
if (left > right) {
return null;
}
//mid = 4
int mid = (left + right) / 2;
//nums[mid] = 4
TreeNode root = new TreeNode(nums[mid]);
root.left =
//遞歸進(jìn)入 left = 0, right = 3
if (left > right) {
return null;
}
//mid = 1
int mid = (left + right) / 2;
//nums[mid] = 1
TreeNode root = new TreeNode(nums[mid]);
root.left =
//遞歸進(jìn)入 left = 0, right = 0
if (left > right) {
return null;
}
//mid = 0
int mid = (left + right) / 2;
//nums[mid] = 0
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, left, mid - 1);
root.right = helper(nums, mid + 1, right);
root.right = helper(nums, mid + 1, right);
root.right = helper(nums, mid + 1, right);
//第一次進(jìn)入 left = 0, right = 8
if (left > right) {
return null;
}
//mid = 4
int mid = (left + right) / 2;
//nums[mid] = 4
TreeNode root = new TreeNode(nums[mid]);
root.left =
//遞歸進(jìn)入 left = 0, right = 3
if (left > right) {
return null;
}
//mid = 1
int mid = (left + right) / 2;
//nums[mid] = 1
TreeNode root = new TreeNode(nums[mid]);
root.left =
//遞歸進(jìn)入 left = 0, right = 0
if (left > right) {
return null;
}
//mid = 0
int mid = (left + right) / 2;
//nums[mid] = 0
TreeNode root = new TreeNode(nums[mid]);
root.left =
//遞歸進(jìn)入 left = 0, right = -1
if (left > right) {
//回溯
return null;
}
root.right = helper(nums, mid + 1, right);
root.right = helper(nums, mid + 1, right);
root.right = helper(nums, mid + 1, right);
//第一次進(jìn)入 left = 0, right = 8
if (left > right) {
return null;
}
//mid = 4
int mid = (left + right) / 2;
//nums[mid] = 4
TreeNode root = new TreeNode(nums[mid]);
root.left =
//遞歸進(jìn)入 left = 0, right = 3
if (left > right) {
return null;
}
//mid = 1
int mid = (left + right) / 2;
//nums[mid] = 1
TreeNode root = new TreeNode(nums[mid]);
root.left =
//遞歸進(jìn)入 left = 0, right = 0
if (left > right) {
return null;
}
//mid = 0
int mid = (left + right) / 2;
//nums[mid] = 0
TreeNode root = new TreeNode(nums[mid]);
root.left = null
root.right =
//進(jìn)入遞歸 left = 1,right = 0
if (left > right) {
//回溯
return null;
}
root.right = helper(nums, mid + 1, right);
root.right = helper(nums, mid + 1, right);
//第一次進(jìn)入 left = 0, right = 8
if (left > right) {
return null;
}
//mid = 4
int mid = (left + right) / 2;
//nums[mid] = 4
TreeNode root = new TreeNode(nums[mid]);
root.left =
//遞歸進(jìn)入 left = 0, right = 3
if (left > right) {
return null;
}
//mid = 1
int mid = (left + right) / 2;
//nums[mid] = 1
TreeNode root = new TreeNode(nums[mid]);
root.left = {0, null, null}
root.right = helper(nums, mid + 1, right);
root.right = helper(nums, mid + 1, right);
//第一次進(jìn)入 left = 0, right = 8
if (left > right) {
return null;
}
//mid = 4
int mid = (left + right) / 2;
//nums[mid] = 4
TreeNode root = new TreeNode(nums[mid]);
root.left =
//遞歸進(jìn)入 left = 0, right = 3
if (left > right) {
return null;
}
//mid = 1
int mid = (left + right) / 2;
//nums[mid] = 1
TreeNode root = new TreeNode(nums[mid]);
root.left = {0, null, null}
root.right =
//遞歸進(jìn)入 left = 2, right = 3
if (left > right) {
return null;
}
//mid = 2
int mid = (left + right) / 2;
//nums[mid] = 2
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, left, mid - 1);
root.right = helper(nums, mid + 1, right);
root.right = helper(nums, mid + 1, right);
//第一次進(jìn)入 left = 0, right = 8
if (left > right) {
return null;
}
//mid = 4
int mid = (left + right) / 2;
//nums[mid] = 4
TreeNode root = new TreeNode(nums[mid]);
root.left =
//遞歸進(jìn)入 left = 0, right = 3
if (left > right) {
return null;
}
//mid = 1
int mid = (left + right) / 2;
//nums[mid] = 1
TreeNode root = new TreeNode(nums[mid]);
root.left = {0, null, null}
root.right =
//遞歸進(jìn)入 left = 2, right = 3
if (left > right) {
return null;
}
//mid = 2
int mid = (left + right) / 2;
//nums[mid] = 2
TreeNode root = new TreeNode(nums[mid]);
root.left =
//遞歸進(jìn)入 left = 2, right = 1
if (left > right) {
//回溯
return null;
}
root.right = helper(nums, mid + 1, right);
root.right = helper(nums, mid + 1, right);
//第一次進(jìn)入 left = 0, right = 8
if (left > right) {
return null;
}
//mid = 4
int mid = (left + right) / 2;
//nums[mid] = 4
TreeNode root = new TreeNode(nums[mid]);
root.left =
//遞歸進(jìn)入 left = 0, right = 3
if (left > right) {
return null;
}
//mid = 1
int mid = (left + right) / 2;
//nums[mid] = 1
TreeNode root = new TreeNode(nums[mid]);
root.left = {0, null, null}
root.right =
//遞歸進(jìn)入 left = 2, right = 3
if (left > right) {
return null;
}
//mid = 2
int mid = (left + right) / 2;
//nums[mid] = 2
TreeNode root = new TreeNode(nums[mid]);
root.left = null
root.right =
//遞歸進(jìn)入 left = 3 , right = 3
if (left > right) {
return null;
}
//mid = 3
int mid = (left + right) / 2;
//nums[mid] = 3
TreeNode root = new TreeNode(nums[mid]);
root.left = helper(nums, left, mid - 1);
root.right = helper(nums, mid + 1, right);
root.right = helper(nums, mid + 1, right);
//第一次進(jìn)入 left = 0, right = 8
if (left > right) {
return null;
}
//mid = 4
int mid = (left + right) / 2;
//nums[mid] = 4
TreeNode root = new TreeNode(nums[mid]);
root.left =
//遞歸進(jìn)入 left = 0, right = 3
if (left > right) {
return null;
}
//mid = 1
int mid = (left + right) / 2;
//nums[mid] = 1
TreeNode root = new TreeNode(nums[mid]);
root.left = {0, null, null}
root.right =
//遞歸進(jìn)入 left = 2, right = 3
if (left > right) {
return null;
}
//mid = 2
int mid = (left + right) / 2;
//nums[mid] = 2
TreeNode root = new TreeNode(nums[mid]);
root.left = null
root.right =
//遞歸進(jìn)入 left = 3 , right = 3
if (left > right) {
return null;
}
//mid = 3
int mid = (left + right) / 2;
//nums[mid] = 3
TreeNode root = new TreeNode(nums[mid]);
root.left =
//遞歸進(jìn)入 left = 3, 2
if (left > right) {
//回溯
return null;
}
root.right = helper(nums, mid + 1, right);
root.right = helper(nums, mid + 1, right);
//第一次進(jìn)入 left = 0, right = 8
if (left > right) {
return null;
}
//mid = 4
int mid = (left + right) / 2;
//nums[mid] = 4
TreeNode root = new TreeNode(nums[mid]);
root.left =
//遞歸進(jìn)入 left = 0, right = 3
if (left > right) {
return null;
}
//mid = 1
int mid = (left + right) / 2;
//nums[mid] = 1
TreeNode root = new TreeNode(nums[mid]);
root.left = {0, null, null}
root.right =
//遞歸進(jìn)入 left = 2, right = 3
if (left > right) {
return null;
}
//mid = 2
int mid = (left + right) / 2;
//nums[mid] = 2
TreeNode root = new TreeNode(nums[mid]);
root.left = null
root.right =
//遞歸進(jìn)入 left = 3 , right = 3
if (left > right) {
return null;
}
//mid = 3
int mid = (left + right) / 2;
//nums[mid] = 3
TreeNode root = new TreeNode(nums[mid]);
root.left = null
root.right =
//遞歸進(jìn)入 left = 4, right = 3
if (left > right) {
//回溯
return null;
}
root.right = helper(nums, mid + 1, right);
//第一次進(jìn)入 left = 0, right = 8
if (left > right) {
return null;
}
//mid = 4
int mid = (left + right) / 2;
//nums[mid] = 4
TreeNode root = new TreeNode(nums[mid]);
root.left =
//遞歸進(jìn)入 left = 0, right = 3
if (left > right) {
return null;
}
//mid = 1
int mid = (left + right) / 2;
//nums[mid] = 1
TreeNode root = new TreeNode(nums[mid]);
root.left = {0, null, null}
root.right =
//遞歸進(jìn)入 left = 2, right = 3
if (left > right) {
return null;
}
//mid = 2
int mid = (left + right) / 2;
//nums[mid] = 2
TreeNode root = new TreeNode(nums[mid]);
root.left = null
root.right = {3, null, null}
root.right = helper(nums, mid + 1, right);
//第一次進(jìn)入 left = 0, right = 8
if (left > right) {
return null;
}
//mid = 4
int mid = (left + right) / 2;
//nums[mid] = 4
TreeNode root = new TreeNode(nums[mid]);
root.left =
//遞歸進(jìn)入 left = 0, right = 3
if (left > right) {
return null;
}
//mid = 1
int mid = (left + right) / 2;
//nums[mid] = 1
TreeNode root = new TreeNode(nums[mid]);
root.left = {0, null, null}
root.right = {2, null, {3, null, null}}
root.right = helper(nums, mid + 1, right);
//第一次進(jìn)入 left = 0, right = 8
if (left > right) {
return null;
}
//mid = 4
int mid = (left + right) / 2;
//nums[mid] = 4
TreeNode root = new TreeNode(nums[mid]);
root.left = {1, {0, null, null}, {2, null, {3, null, null}}}
root.right = helper(nums, mid + 1, right);
萬(wàn)卷古今消永日筐眷，一窗昏曉送流年
【白話譯文】
在萬(wàn)卷書(shū)中消磨自己整整的一天，南窗下讓自己生命的河流靜靜地流過(guò)
手敲不易习柠，點(diǎn)個(gè)贊唄
