如何将有序数组转换为二叉搜索树
程序员文章站
2022-03-14 14:52:20
...
本篇文章给大家带来的内容是关于如何将有序数组转换为二叉搜索树,有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。
题目
代码
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: //等价于中序遍历的数组再恢复成树 TreeNode* sortedArrayToBST(vector<int>& nums) { if(nums.size()==0) return nullptr; if(nums.size()==1) return new TreeNode(nums[0]); int middle=nums.size()/2; auto root=new TreeNode(nums[middle]); vector<int> left(nums.begin(),nums.begin()+middle); vector<int> right(nums.begin()+middle+1,nums.end()); root->left=sortedArrayToBST(left); root->right=sortedArrayToBST(right); return root; } };
思路
用递归的方式,每次将数组中中间的那个值当作是当前结点,然后左边的再递归下去生成左孩子,右边的递归下去生成右孩子。
以上就是如何将有序数组转换为二叉搜索树的详细内容,更多请关注其它相关文章!
上一篇: ES6中模块化的使用介绍(代码示例)