怎么就能構(gòu)造成二叉樹呢？

經(jīng)常有錄友問，二叉樹的題目中輸入用例，在ACM模式下應(yīng)該怎么構(gòu)造呢？

力扣上的題目，輸入用例就給了一個數(shù)組，怎么就能構(gòu)造成二叉樹呢？

這次就給大家好好講一講！

就拿最近公眾號上 二叉樹的打卡題目來說：

538.把二叉搜索樹轉(zhuǎn)換為累加樹

其輸入用例，就是用一個數(shù)組來表述 二叉樹，如下：

一直跟著公眾號學(xué)算法的錄友 應(yīng)該知道，我在二叉樹：構(gòu)造二叉樹登場！，已經(jīng)講過，只有 中序與后序 和 中序和前序 可以確定一顆唯一的二叉樹。前序和后序是不能確定唯一的二叉樹的。

那么538.把二叉搜索樹轉(zhuǎn)換為累加樹的示例中，為什么，一個序列（數(shù)組或者是字符串）就可以確定二叉樹了呢？

很明顯，是后臺直接明確了構(gòu)造規(guī)則。

再看一下 這個 輸入序列 和 對應(yīng)的二叉樹。

從二叉樹 推導(dǎo)到 序列，大家可以發(fā)現(xiàn)這就是層序遍歷。

但從序列 推導(dǎo)到 二叉樹，很多同學(xué)就看不懂了，這得怎么轉(zhuǎn)換呢。

我在關(guān)于二叉樹，你該了解這些！已經(jīng)詳細講過，二叉樹可以有兩種存儲方式，一種是 鏈式存儲，另一種是順序存儲。

鏈式存儲，就是大家熟悉的二叉樹，用指針指向左右孩子。

順序存儲，就是用一個數(shù)組來存二叉樹，其方式如圖所示：

那么此時大家是不是應(yīng)該知道了，數(shù)組如何轉(zhuǎn)化成 二叉樹了。如果父節(jié)點的數(shù)組下標是i，那么它的左孩子下標就是i * 2 + 1，右孩子下標就是 i * 2 + 2。

那么這里又有同學(xué)疑惑了，這些我都懂了，但我還是不知道 應(yīng)該 怎么構(gòu)造。

來，咱上代碼。昨天晚上 速度敲了一遍實現(xiàn)代碼。

具體過程看注釋：

//根據(jù)數(shù)組構(gòu)造二叉樹
TreeNode*construct_binary_tree(constvector<int>&vec){
vectorvecTree(vec.size(),NULL);
TreeNode*root=NULL;
//把輸入數(shù)值數(shù)組，先轉(zhuǎn)化為二叉樹節(jié)點數(shù)組
for(inti=0;iNULL;
if(vec[i]!=-1)node=newTreeNode(vec[i]);//數(shù)組中用-1表示null
vecTree[i]=node;
if(i==0)root=node;
}
//遍歷一遍，根據(jù)規(guī)則左右孩子賦值就可以了
//注意這里結(jié)束規(guī)則是i*2+2
for(inti=0;i*2+2if(vecTree[i]!=NULL){
//線性存儲轉(zhuǎn)連式存儲關(guān)鍵邏輯
vecTree[i]->left=vecTree[i*2+1];
vecTree[i]->right=vecTree[i*2+2];
}
}
returnroot;
}

這個函數(shù)最后返回的 指針就是 根節(jié)點的指針， 這就是 傳入二叉樹的格式了，也就是 力扣上的用例輸入格式，如圖：

也有不少同學(xué)在做ACM模式的題目，就經(jīng)常疑惑：

• 讓我傳入數(shù)值，我會！
• 讓我傳入數(shù)組，我會！
• 讓我傳入鏈表，我也會！
• 讓我傳入二叉樹，我懵了，啥？傳入二叉樹？二叉樹怎么傳？

其實傳入二叉樹，就是傳入二叉樹的根節(jié)點的指針，和傳入鏈表都是一個邏輯。

這種現(xiàn)象主要就是大家對ACM模式過于陌生，說實話，ACM模式才真正的考察代碼能力（注意不是算法能力），而 力扣的核心代碼模式 總有一種 不夠徹底的感覺。

所以，如果大家對ACM模式不夠了解，一定要多去練習(xí)！

那么以上的代碼，我們根據(jù)數(shù)組構(gòu)造二叉樹，接來下我們在 把 這個二叉樹打印出來，看看是不是 我們輸入的二叉樹結(jié)構(gòu)，這里就用到了層序遍歷，我們在二叉樹：層序遍歷登場！中講過。

完整測試代碼如下：

#include
#include
#include
usingnamespacestd;

structTreeNode{
intval;
TreeNode*left;
TreeNode*right;
TreeNode(intx):val(x),left(NULL),right(NULL){}
};

//根據(jù)數(shù)組構(gòu)造二叉樹
TreeNode*construct_binary_tree(constvector<int>&vec){
vectorvecTree(vec.size(),NULL);
TreeNode*root=NULL;
for(inti=0;iNULL;
if(vec[i]!=-1)node=newTreeNode(vec[i]);
vecTree[i]=node;
if(i==0)root=node;
}
for(inti=0;i*2+2if(vecTree[i]!=NULL){
vecTree[i]->left=vecTree[i*2+1];
vecTree[i]->right=vecTree[i*2+2];
}
}
returnroot;
}

//層序打印打印二叉樹
voidprint_binary_tree(TreeNode*root){
queueque;
if(root!=NULL)que.push(root);
vector<vector<int>>result;
while(!que.empty()){
intsize=que.size();
vector<int>vec;
for(inti=0;iif(node!=NULL){
vec.push_back(node->val);
que.push(node->left);
que.push(node->right);
}
//這里的處理邏輯是為了把null節(jié)點打印出來，用-1表示null
elsevec.push_back(-1);
}
result.push_back(vec);
}
for(inti=0;ifor(intj=0;jcout<"";
}
cout<endl;
}
}

intmain(){
//注意本代碼沒有考慮輸入異常數(shù)據(jù)的情況
//用-1來表示null
vector<int>vec={4,1,6,0,2,5,7,-1,-1,-1,3,-1,-1,-1,8};
TreeNode*root=construct_binary_tree(vec);
print_binary_tree(root);
}

可以看出我們傳入的數(shù)組是：{4,1,6,0,2,5,7,-1,-1,-1,3,-1,-1,-1,8} ， 這里是用 -1 來表示null，

和538.把二叉搜索樹轉(zhuǎn)換為累加樹中的輸入是一樣的

這里可能又有同學(xué)疑惑，你這不一樣啊，題目是null，你為啥用-1。

用-1 表示null為了方便舉例，如果非要和 力扣輸入一樣一樣的，就是簡單的字符串處理，把null 替換為 -1 就行了。

在來看，測試代碼輸出的效果：

可以看出和 題目中輸入用例 這個圖 是一樣一樣的。只不過題目中圖沒有把 空節(jié)點 畫出來而已。

大家可以拿我的代碼去測試一下，跑一跑。

注意：我的測試代碼，并沒有處理輸入異常的情況（例如輸入空數(shù)組之類的），處理各種輸入異常，大家可以自己去練練。