careercup-树与图 4.3

4.3 给定一个有序整数数组，元素各不相同按升序排列，编写一个算法，创建一棵高度最小的二叉查找树。

解答

想要使构建出来的二叉树高度最小，那么对于任意结点，它的左子树和右子树的结点数量应该相当。比如，当我们将一个数放在根结点，那么理想情况是，我们把数组中剩下的数对半分，一半放在根结点的左子树，另一半放在根结点的右子树。我们可以定义不同的规则来决定这些数怎样对半分，不过最简单的方法就是取得有序数组中中间那个数，然后把小于它的放在它的左子树，大于它的放在它的右子树。不断地递归操作即可构造这样一棵最小高度二叉树。

与leetcode类似题目：https://oj.leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

C++实现代码：

#include<vector>

#include<iostream>

using namespace std;

struct TreeNode

{

    int val;

    TreeNode *left;

    TreeNode *right;

    TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

TreeNode* helper(vector<int>::iterator begin,vector<int>::iterator end)

{

    TreeNode *root=NULL;

    if(begin+==end)

        return new TreeNode(*begin);

    if(begin>=end)

        return NULL;

    int mid=(end-begin)/;

    root=new TreeNode(*begin+mid);

    root->left=helper(begin,begin+mid);

    root->right=helper(begin+mid+,end);

    return root;

}

TreeNode* createAVL(vector<int> &vec)

{

    if(vec.empty())

        return NULL;

    return helper(vec.begin(),vec.end());

}

void inorder(TreeNode *root)

{

    if(root)

    {

        inorder(root->left);

        cout<<root->val<<" ";

        inorder(root->right);

    }

}

int maxDepth(TreeNode *root)

{

    if(root)

    {

        if(root->left==NULL&&root->right==NULL)

            return ;

        int leftDepth=maxDepth(root->left);

        int rightDepth=maxDepth(root->right);

        return leftDepth>= rightDepth ?(leftDepth+):(rightDepth+);

    }

    return ;

}

int main()

{

    vector<int> vec= {,,,,,,,,,};

    TreeNode *root=createAVL(vec);

    inorder(root);

    cout<<endl;

    cout<<maxDepth(root)<<endl;

}

巴特西

careercup-树与图 4.3

解答

最新文章

热门文章