108.将有序数组转换为二叉搜索树.md

108. 将有序数组转换为二叉搜索树

url

题目

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

返回其自底向上的层序遍历为：
      0
     / \
   -3   9
   /   /
 -10  5

方法

二叉树中序遍历的逆过程哦

• 前序遍历：根结点 ---> 左子树 ---> 右子树
• 中序遍历：左子树---> 根结点 ---> 右子树
• 后序遍历：左子树 ---> 右子树 ---> 根结点

code

js

let sortedArrayToBST = nums => {
    return nums === null ? null : buildTree(nums, 0, nums.length - 1);
}

let buildTree = (nums, l, r) => {
    if (l > r) return null;
    let m = Math.floor(l + (r - l) / 2);
    let root = TreeNode(nums[m]);
    root.left = buildTree(nums, l, m - 1);
    root.right = buildTree(nums, m + 1, r);
    return root;
}

go

func sortedArrayToBST(nums []int) *TreeNode {
	var buildTree func (nums[] int, l, r int) *TreeNode
	buildTree = func (nums[] int, l, r int) *TreeNode {
		if l > r {
		return nil
	}
		m := l + (r - l) / 2
		root := &TreeNode{Val: nums[m]}
		root.Left = buildTree(nums, l, m - 1)
		root.Right = buildTree(nums, m + 1, l)
		return root
	}
	if nums == nil || len(nums) == 0 {
		return nil
	}
	return buildTree(nums, 0, len(nums) - 1)
}

java

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return nums == null ? null : buildTree(nums, 0, nums.length - 1);
    }
    private TreeNode buildTree(int[] nums, int l, int r) {
        if(l > r) return null;
        int m = l + (r - l) / 2;
        TreeNode root = new TreeNode(nums[m]);
        root.left = buildTree(nums, l, m - 1);
        root.right = buildTree(nums, m + 1, r);
        return root;
    }
}