108. Convert Sorted Array to Binary Search Tree

题干简述：

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡:二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

解题思路

审完题，我注意到题目是让我们将一个升序的数组转化为一个 BST，而 BST 的特性就是其进行中序遍历后，会转化为一个升序的数组；换言之，题目的实质是让我们坐中序遍历的逆操作而已。不得不说，一开始看这道题给的示例，给我整不会了。

image

乍一看，这个例子没什么问题呀，完美符合 BST 的特征，中序遍历的结果也和 nums 数组一致，为什么要转化为下图所示的树呢？

image

让我们重新来看下题目：给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。题干中有一个很重要的条件，高度平衡。什么叫高度平衡？二叉树满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」。翻译一下，就是我们在中序遍历倒推树的时候，每棵树的根结点 root，都得是数组的中间那个结点。只有这样，才能保证左右子树的高度差不会超过1。这样，就合理的解释了为什么经过转化后树的结构发生了变化。

明确了解题思路之后，通过递归倒推中序遍历即可，大家可以参考如下代码，很简单，就不详细解释了。

题解

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    return dfs(nums, 0, nums.length - 1);
};

const dfs = (nums, low, high) => {
    if (low > high) return null;
  	// 取数组中间下标
    const mid = Math.floor(low + (high - low) / 2);
    let root = new TreeNode(nums[mid]);
		// 生成 root 左右子树，限定取结点范围为 root 结点左右侧的结点
    root.left = dfs(nums, low, mid - 1);
    root.right = dfs(nums, mid + 1, high);
    return root;
};

Q.E.D.

Take it easy