[leetCode]Convert Sorted Array to Binary Search Tree-白红宇

[leetCode]Convert Sorted Array to Binary Search Tree

阅读量：5257 次

发布时间：2019-06-14

本文共 958 字，大约阅读时间需要 3 分钟。

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

构建平衡二叉排序树（AVL）

注意到平衡二叉排序树的根节点是数组的中间点就好，之后是递归。

1 #include 
     
       2 #include 
      
        3 using namespace std; 4  5 struct TreeNode { 6     int val; 7     TreeNode *left; 8     TreeNode *right; 9     TreeNode(int x) : val(x), left(NULL), right(NULL) {}10 };11 class Solution {12 public:13     TreeNode *sortedArrayToBST(vector
       
         &num) {14         TreeNode *head = build(num,0,num.size()-1);15         return head;16     }17     TreeNode *build(vector
        
          &num, int low, int high){18         int headnum = (low+high)/2;19         if(low > high) return NULL;20         TreeNode *head = new TreeNode(num[headnum]);21         head->left = build(num, low,headnum-1);22         head->right = build(num,headnum+1,high);23         return head;24     }25 };