【Check 50】2024-04-12 - 108. 将有序数组转换为二叉搜索树

[larscheng]

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

[larscheng]

思路

• 递归

中序遍历结果即为升序数组，要求二叉平衡树，则可以确定根节点

• 奇数个元素：中间元素即为根节点
• 偶数个元素：中间位置前一位or中间位置后一位为根节点

确定了中间节点，则可通过递归，继续构造根节点下的左/右子树

代码

class Solution {
    //O(n)/O(logn)
    //中序遍历：升序数组，+二叉平衡数=》可以确定根节点，根节点左右的数组元素均为左右子树
    public TreeNode sortedArrayToBST(int[] nums) {
        return convert(nums,0,nums.length-1);
    }

    private TreeNode convert(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        //中间位置左边的数作为根节点
        int mid = left+(right-left)/2;
        // 中间位置右边的数作为根节点
        // int mid = left+(right-left+1)/2

        TreeNode root = new TreeNode(nums[mid]);
        root.left = convert(nums,left,mid-1);
        root.right = convert(nums,mid+1,right);
        return root;
    }
}

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(logn)