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

发表于 | 分类于 | 阅读次数:
字数统计: 183 | 阅读时长 ≈ 1

将有序数组转换成二叉搜索树

LeetCode 108

英文版

中文版

本题是用的树的中序遍历，和剑指offer中 剑指Offer(33) 二叉搜索树的后续遍历序列 类似，不过本题用的是后续遍历，但都是递归思想。

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * @description:
 * @author: rhsphere
 * @since: 2019-11-05 18:35 by jdk 1.8
 */
public class SortedArrayToBST {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length <= 0)
            return null;
        return sortedArrayToBST(nums, 0, nums.length-1);
    }
    
    private TreeNode sortedArrayToBST(int[] nums, int start, int end) {

        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        if(start < mid)
            root.left = sortedArrayToBST(nums, start, mid-1);
        if (mid < end)
            root.right = sortedArrayToBST(nums, mid + 1, end);
        return root;
    }
}

题目

0%