7(108) 將有序數組轉換為二叉搜索樹

描述

將一個按照升序排列的有序數組，轉換為一棵高度平衡二叉搜索樹。

本題中，一個高度平衡二叉樹是指一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1。

示例

給定有序數組: [-10,-3,0,5,9],一個可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面這個高度平衡二叉搜索樹：0/ -3 9/ /-10 5

Description

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

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example

Given the sorted array: [-10,-3,0,5,9],One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:0/ -3 9/ /-10 5

BitDance Amazon Microsoft Adobe Apple Google Tencent Mi HuaWei VMware

解題

二叉搜索樹 BST(Binary Search Tree) 又稱為二叉查找樹 二叉排序樹 二叉搜索樹或者是一棵空的樹 或者是具有以下特征的樹: 1. 若左子樹非空 則左子樹上所有的結點key_val均小于根節點的key_val 2. 若右子樹非空 則右子樹上所有的結點key_val均大于根節點的key_val 3. 左右子樹本身也是二叉搜索樹

因此 對二叉搜索樹進行中序遍歷 得到的一定是一個遞增的有序序列

#include <iostream>// SortedArray to BST #include <vector> #include <queue> using namespace std; struct TreeNode{int val;TreeNode *left;TreeNode *right;TreeNode(int x):val(x),left(NULL),right(NULL) {} }; TreeNode* levelCreateBinaryTree(const vector<int> &nums,int len,int index){//層序創建二叉樹index為位置序號TreeNode *root=NULL;if(index<len&&nums[index]!=-1){root = new TreeNode(nums[index]);root->left = levelCreateBinaryTree(nums,len,2*index+1);root->right= levelCreateBinaryTree(nums,len,2*index+2);}return root; } void PrintMartrix(vector<vector<int>>& res){//打印二維數組for(int i=0;i<res.size();++i){cout<<"[";for(int j=0;j<res[i].size();++j){cout<<" "<<res[i][j]<<" ";}cout<<"]"<<endl;} } class Solution { public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;if(!root) return res;queue<TreeNode* > Tree;Tree.push(root);while(!Tree.empty()){vector<int> temp;int len=Tree.size();while(len--){TreeNode *pNode=Tree.front();Tree.pop();temp.push_back(pNode->val);if(pNode->left) Tree.push(pNode->left);if(pNode->right) Tree.push(pNode->right);}res.push_back(temp);}return res;}vector<int> res;vector<int> inorderTraversal(TreeNode* root) {//遞歸算法if(root!=NULL){inorderTraversal(root->left);res.push_back(root->val);inorderTraversal(root->right);}return res;}TreeNode* sortedArrayToBST(vector<int>& nums) {if(nums.size()==0) return NULL;if(nums.size()==1) return new TreeNode(nums[0]);int mid=nums.size()/2;TreeNode* node=new TreeNode(nums[mid]);vector<int>::const_iterator first;vector<int>::const_iterator last;first=nums.begin();last=nums.begin()+mid;vector<int> v_temp(first,last);node->left=sortedArrayToBST(v_temp);if(mid==nums.size()-1) node->right=NULL;else{first=nums.begin()+mid+1;last=nums.end();vector<int> v_temp(first,last);node->right=sortedArrayToBST(v_temp);}return node;} }; int main(){vector<int> nums={0,1,2,3,4,5};//示例 值為-1代表所在位置為空值int len=nums.size();Solution answer;TreeNode *root=answer.sortedArrayToBST(nums);vector<vector<int>> res=answer.levelOrder(root);PrintMartrix(res);//打印層序遍歷的二維數組vector<int> print=answer.inorderTraversal(root);for(auto x:print) cout<<x<<" ";//打印中序遍歷的序列return 0; }

總結

以上是生活随笔為你收集整理的将字符串转换为数组_LeetCode 树 108.将有序数组转换为二叉搜索树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。