經常有錄友問，二叉樹的題目中輸入用例，在ACM模式下應該怎么構造呢？

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

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

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

538.把二叉搜索樹轉換為累加樹

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

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

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

很明顯，是后臺直接明確了構造規則。

再看一下 這個 輸入序列 和 對應的二叉樹。

從二叉樹 推導到 序列，大家可以發現這就是層序遍歷。

但從序列 推導到 二叉樹，很多同學就看不懂了，這得怎么轉換呢。

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

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

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

那么此時大家是不是應該知道了，數組如何轉化成 二叉樹了。如果父節點的數組下標是i，那么它的左孩子下標就是i * 2 + 1，右孩子下標就是 i * 2 + 2。

那么這里又有同學疑惑了，這些我都懂了，但我還是不知道 應該 怎么構造。

來，咱上代碼。昨天晚上 速度敲了一遍實現代碼。

具體過程看注釋：

//根據數組構造二叉樹
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]);//數組中用-1表示null
vecTree[i]=node;
if(i==0)root=node;
}
//遍歷一遍，根據規則左右孩子賦值就可以了
//注意這里結束規則是i*2+2
for(inti=0;i*2+2if(vecTree[i]!=NULL){
//線性存儲轉連式存儲關鍵邏輯
vecTree[i]->left=vecTree[i*2+1];
vecTree[i]->right=vecTree[i*2+2];
}
}
returnroot;
}

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

也有不少同學在做ACM模式的題目，就經常疑惑：

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

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

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

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

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

完整測試代碼如下：

#include
#include
#include
usingnamespacestd;

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

//根據數組構造二叉樹
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節點打印出來，用-1表示null
elsevec.push_back(-1);
}
result.push_back(vec);
}
for(inti=0;ifor(intj=0;jcout<"";
}
cout<endl;
}
}

intmain(){
//注意本代碼沒有考慮輸入異常數據的情況
//用-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);
}

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

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

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

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

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

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

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

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