首页 > 数据结构 > 树形结构 > LeetCode-Convert Sorted Array to Binary Search Tree[二叉树]
2014
11-18

LeetCode-Convert Sorted Array to Binary Search Tree[二叉树]

Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

标签: Tree Depth-first Search
分析

二分法。

代码1

// LeetCode, Convert Sorted Array to Binary Search Tree
// 分治法,时间复杂度O(n),空间复杂度O(logn)
class Solution {
public:
    TreeNode* sortedArrayToBST (vector<int>& num) {
        return sortedArrayToBST(num.begin(), num.end());
    }

    template<typename RandomAccessIterator>
    TreeNode* sortedArrayToBST (RandomAccessIterator first,
            RandomAccessIterator last) {
        const auto length = distance(first, last);

        if (length <= 0) return nullptr;  // 终止条件

        // 三方合并
        auto mid = first + length / 2;
        TreeNode* root = new TreeNode (*mid);
        root->left = sortedArrayToBST(first, mid);
        root->right = sortedArrayToBST(mid + 1, last);

        return root;
    }
};

Java代码:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public static TreeNode sortedArrayToBST(int[] num) {
        if(num == null || num.length == 0) return null;
        return sortedArrayToBST(num, 0, num.length-1);
    }

    public static TreeNode sortedArrayToBST(int num[],int start, int end){
        if(start > end ) return null;
        if(start == end) return new TreeNode(num[start]);
        int mid = start + (end-start)/2;
        TreeNode root = new TreeNode(num[mid]);
        root.left = sortedArrayToBST(num, start, mid-1);
        root.right = sortedArrayToBST(num, mid+1, end);
        return root;
    }
}

相关题目
Convert Sorted List to Binary Search Tree


  1. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥