CCI题目4-3:Tree from Sorted Array

By | 2012 年 11 月 24 日

直接二分数组,第一次二分得到的是根节点,对左半部分二分出来的树是左子树,有半部分二分出来的树是右子树,这样递归就可以了。



题目
Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.



代码


//
//  main.cpp
//  CCI.4.3.Tree from Sorted Array
//
//  Created by Qiu Xiangyu on 12-11-24.
//  Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

#include 
#include 
using namespace std;


struct TreeNode {
    int value;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val, TreeNode *l, TreeNode *r) {
        value = val;
        left = l;
        right = r;
    }
    TreeNode(int val = 0) {
        value = val;
        left = NULL;
        right = NULL;
    }
};

TreeNode *buildTreeFromSortedArray(vector &arr, size_t istart, size_t iend) {
    if (istart > iend) {
        return NULL;
    }
    int imid = (istart + iend + 1) / 2;
    TreeNode *root = new TreeNode(arr[imid]);
    root->left = buildTreeFromSortedArray(arr, istart, imid - 1);
    root->right = buildTreeFromSortedArray(arr, imid + 1, iend);
    return root;
}
TreeNode *buildTreeFromSortedArray(vector &arr) {
    return buildTreeFromSortedArray(arr, 0, arr.size() - 1);
}

int main(int argc, const char * argv[])
{
    // insert code here...
    std::cout << "Hello, World!\n";
    vector arr = {1,2,3,4,5,6,7,8,9,10};
    TreeNode *root = buildTreeFromSortedArray(arr);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注