您好,登錄后才能下訂單哦!
二叉樹
在計(jì)算機(jī)科學(xué)中,二叉樹是每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”(left subtree)和“右子樹”(right subtree)。二叉樹常被用于實(shí)現(xiàn)二叉查找樹和二叉堆。
題目描述
二叉樹結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)規(guī)定如下:
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
本題主要采用遞歸思想,解法如下:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin)
{
vector<int> pre_lchild, pre_rchild, vin_lchild, vin_rchild;
int i;
int size = pre.size();
if(size == 0)
return NULL;
TreeNode* root = new TreeNode(pre[0]);
for(i = 0; vin[i] != pre[0]; ++i);
pre_lchild = vector<int>(pre.begin()+1, pre.begin()+i+1);
vin_lchild = vector<int>(vin.begin(), vin.begin()+i);
pre_rchild = vector<int>(pre.begin()+i+1, pre.end());
vin_rchild = vector<int>(vin.begin()+i+1, vin.end());
root->left = reConstructBinaryTree(pre_lchild, vin_lchild);
root->right = reConstructBinaryTree(pre_rchild, vin_rchild);
return root;
}
時(shí)間復(fù)雜度為O(nlogn),空間復(fù)雜度為O(n^2)。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。