怎么就能构造成二叉树呢？
经常有录友问，二叉树的题目中输入用例，在acm模式下应该怎么构造呢？ 力扣上的题目，输入用例就给了一个数组，怎么就能构造成二叉树呢？
这次就给大家好好讲一讲！
就拿最近公众号上 二叉树的打卡题目来说：
538.把二叉搜索树转换为累加树
其输入用例，就是用一个数组来表述 二叉树，如下：
一直跟着公众号学算法的录友 应该知道，我在二叉树：构造二叉树登场！，已经讲过，只有 中序与后序 和 中序和前序 可以确定一颗唯一的二叉树。前序和后序是不能确定唯一的二叉树的。
那么538.把二叉搜索树转换为累加树的示例中，为什么，一个序列（数组或者是字符串）就可以确定二叉树了呢？
很明显，是后台直接明确了构造规则。
再看一下 这个 输入序列 和 对应的二叉树。
从二叉树 推导到 序列，大家可以发现这就是层序遍历。
但从序列 推导到 二叉树，很多同学就看不懂了，这得怎么转换呢。
我在 关于二叉树，你该了解这些！已经详细讲过，二叉树可以有两种存储方式，一种是 链式存储，另一种是顺序存储。
链式存储，就是大家熟悉的二叉树，用指针指向左右孩子。
顺序存储，就是用一个数组来存二叉树，其方式如图所示：
那么此时大家是不是应该知道了，数组如何转化成 二叉树了。如果父节点的数组下标是i，那么它的左孩子下标就是i * 2 + 1，右孩子下标就是 i * 2 + 2。
那么这里又有同学疑惑了，这些我都懂了，但我还是不知道 应该 怎么构造。
来，咱上代码。昨天晚上 速度敲了一遍实现代码。
具体过程看注释：
// 根据数组构造二叉树treenode* construct_binary_tree(const vector& vec) { vector vectree (vec.size(), null); treenode* root = null; // 把输入数值数组，先转化为二叉树节点数组 for (int i = 0; i < vec.size(); i++) { treenode* node = null; if (vec[i] != -1) node = new treenode(vec[i]); // 数组中用-1表示null vectree[i] = node; if (i == 0) root = node; } // 遍历一遍，根据规则左右孩子赋值就可以了 // 注意这里 结束规则是 i * 2 + 2 < vec.size()，避免空指针 for (int i = 0; i * 2 + 2 left = vectree[i * 2 + 1]; vectree[i]->right = vectree[i * 2 + 2]; } } return root;} 这个函数最后返回的 指针就是 根节点的指针， 这就是 传入二叉树的格式了，也就是 力扣上的用例输入格式，如图：
也有不少同学在做acm模式的题目，就经常疑惑：
让我传入数值，我会！ 让我传入数组，我会！ 让我传入链表，我也会！ 让我传入二叉树，我懵了，啥？传入二叉树？二叉树怎么传？ 其实传入二叉树，就是传入二叉树的根节点的指针，和传入链表都是一个逻辑。
这种现象主要就是大家对acm模式过于陌生，说实话，acm模式才真正的考察代码能力（注意不是算法能力），而 力扣的核心代码模式 总有一种 不够彻底的感觉。
所以，如果大家对acm模式不够了解，一定要多去练习！
那么以上的代码，我们根据数组构造二叉树，接来下我们在 把 这个二叉树打印出来，看看是不是 我们输入的二叉树结构，这里就用到了层序遍历，我们在二叉树：层序遍历登场！中讲过。
完整测试代码如下：
#include #include #include using namespace std;struct treenode { int val; treenode *left; treenode *right; treenode(int x) : val(x), left(null), right(null) {}};// 根据数组构造二叉树treenode* construct_binary_tree(const vector& vec) { vector vectree (vec.size(), null); treenode* root = null; for (int i = 0; i < vec.size(); i++) { treenode* node = null; if (vec[i] != -1) node = new treenode(vec[i]); vectree[i] = node; if (i == 0) root = node; } for (int i = 0; i * 2 + 2 left = vectree[i * 2 + 1]; vectree[i]->right = vectree[i * 2 + 2]; } } return root;}// 层序打印打印二叉树void print_binary_tree(treenode* root) { queue que; if (root != null) que.push(root); vector result; while (!que.empty()) { int size = que.size(); vector vec; for (int i = 0; i val); que.push(node->left); que.push(node->right); } // 这里的处理逻辑是为了把null节点打印出来，用-1 表示null else vec.push_back(-1); } result.push_back(vec); } for (int i = 0; i < result.size(); i++) { for (int j = 0; j < result[i].size(); j++) { cout << result[i][j] << ; } cout << endl; }}int main() { // 注意本代码没有考虑输入异常数据的情况 // 用 -1 来表示null vector 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 就行了。
在来看，测试代码输出的效果：
可以看出和 题目中输入用例 这个图 是一样一样的。只不过题目中图没有把 空节点 画出来而已。
大家可以拿我的代码去测试一下，跑一跑。
注意：我的测试代码，并没有处理输入异常的情况（例如输入空数组之类的），处理各种输入异常，大家可以自己去练练。
杀入无人驾驶，英特尔哪能错过“撬动IoT的支点”
汽车空调温度控制系统设计
梦芯科技与纵目科技签署战略合作协议
特斯拉停牌退市的原因、影响及可操作性
康宁认为LCD市场将持续增长
怎么就能构造成二叉树呢？
由python入c难，由c入python易？
初学者如何读懂电子商品的电路图
SDN网络热潮终于停歇 疯狂过后的理性部署
LG Gram展出采用了LG Display的可折叠OLED
7805稳压电源如何12V转5V电路图及接线方式
展望2017 预测全球石墨烯七大趋势
国外知名伺服电机/系统制造商盘点
未来汽车工厂：人类与机器人并肩协作
机床测头应用系列二：自动补偿，万千如一
智能搀扶机器人的设计特点是什么
英国电信O2计划今年在英国5G移动频谱拍卖中获得的2.3Ghz频谱
浙江元宇宙政策发布，杭州灵伴科技打造工业AR新引擎
广东潮州引入RFID等技术对古城区进行改造
【树莓派】使用USB网络摄像头替代Raspberry Pi 相机模块
这次就给大家好好讲一讲！
就拿最近公众号上 二叉树的打卡题目来说：
538.把二叉搜索树转换为累加树
其输入用例，就是用一个数组来表述 二叉树，如下：
一直跟着公众号学算法的录友 应该知道，我在二叉树：构造二叉树登场！，已经讲过，只有 中序与后序 和 中序和前序 可以确定一颗唯一的二叉树。前序和后序是不能确定唯一的二叉树的。
那么538.把二叉搜索树转换为累加树的示例中，为什么，一个序列（数组或者是字符串）就可以确定二叉树了呢？
很明显，是后台直接明确了构造规则。
再看一下 这个 输入序列 和 对应的二叉树。
从二叉树 推导到 序列，大家可以发现这就是层序遍历。
但从序列 推导到 二叉树，很多同学就看不懂了，这得怎么转换呢。
我在 关于二叉树，你该了解这些！已经详细讲过，二叉树可以有两种存储方式，一种是 链式存储，另一种是顺序存储。
链式存储，就是大家熟悉的二叉树，用指针指向左右孩子。
顺序存储，就是用一个数组来存二叉树，其方式如图所示：
那么此时大家是不是应该知道了，数组如何转化成 二叉树了。如果父节点的数组下标是i，那么它的左孩子下标就是i * 2 + 1，右孩子下标就是 i * 2 + 2。
那么这里又有同学疑惑了，这些我都懂了，但我还是不知道 应该 怎么构造。
来，咱上代码。昨天晚上 速度敲了一遍实现代码。
具体过程看注释：
// 根据数组构造二叉树treenode* construct_binary_tree(const vector& vec) { vector vectree (vec.size(), null); treenode* root = null; // 把输入数值数组，先转化为二叉树节点数组 for (int i = 0; i < vec.size(); i++) { treenode* node = null; if (vec[i] != -1) node = new treenode(vec[i]); // 数组中用-1表示null vectree[i] = node; if (i == 0) root = node; } // 遍历一遍，根据规则左右孩子赋值就可以了 // 注意这里 结束规则是 i * 2 + 2 < vec.size()，避免空指针 for (int i = 0; i * 2 + 2 left = vectree[i * 2 + 1]; vectree[i]->right = vectree[i * 2 + 2]; } } return root;} 这个函数最后返回的 指针就是 根节点的指针， 这就是 传入二叉树的格式了，也就是 力扣上的用例输入格式，如图：
也有不少同学在做acm模式的题目，就经常疑惑：
让我传入数值，我会！ 让我传入数组，我会！ 让我传入链表，我也会！ 让我传入二叉树，我懵了，啥？传入二叉树？二叉树怎么传？ 其实传入二叉树，就是传入二叉树的根节点的指针，和传入链表都是一个逻辑。
这种现象主要就是大家对acm模式过于陌生，说实话，acm模式才真正的考察代码能力（注意不是算法能力），而 力扣的核心代码模式 总有一种 不够彻底的感觉。
所以，如果大家对acm模式不够了解，一定要多去练习！
那么以上的代码，我们根据数组构造二叉树，接来下我们在 把 这个二叉树打印出来，看看是不是 我们输入的二叉树结构，这里就用到了层序遍历，我们在二叉树：层序遍历登场！中讲过。
完整测试代码如下：
#include #include #include using namespace std;struct treenode { int val; treenode *left; treenode *right; treenode(int x) : val(x), left(null), right(null) {}};// 根据数组构造二叉树treenode* construct_binary_tree(const vector& vec) { vector vectree (vec.size(), null); treenode* root = null; for (int i = 0; i < vec.size(); i++) { treenode* node = null; if (vec[i] != -1) node = new treenode(vec[i]); vectree[i] = node; if (i == 0) root = node; } for (int i = 0; i * 2 + 2 left = vectree[i * 2 + 1]; vectree[i]->right = vectree[i * 2 + 2]; } } return root;}// 层序打印打印二叉树void print_binary_tree(treenode* root) { queue que; if (root != null) que.push(root); vector
和 538.把二叉搜索树转换为累加树 中的输入是一样的
这里可能又有同学疑惑，你这不一样啊，题目是null，你为啥用-1。
用-1 表示null为了方便举例，如果非要和 力扣输入一样一样的，就是简单的字符串处理，把null 替换为 -1 就行了。
在来看，测试代码输出的效果：
可以看出和 题目中输入用例 这个图 是一样一样的。只不过题目中图没有把 空节点 画出来而已。
大家可以拿我的代码去测试一下，跑一跑。
注意：我的测试代码，并没有处理输入异常的情况（例如输入空数组之类的），处理各种输入异常，大家可以自己去练练。
杀入无人驾驶，英特尔哪能错过“撬动IoT的支点”
汽车空调温度控制系统设计
梦芯科技与纵目科技签署战略合作协议
特斯拉停牌退市的原因、影响及可操作性
康宁认为LCD市场将持续增长
怎么就能构造成二叉树呢？
由python入c难，由c入python易？
初学者如何读懂电子商品的电路图
SDN网络热潮终于停歇 疯狂过后的理性部署
LG Gram展出采用了LG Display的可折叠OLED
7805稳压电源如何12V转5V电路图及接线方式
展望2017 预测全球石墨烯七大趋势
国外知名伺服电机/系统制造商盘点
未来汽车工厂：人类与机器人并肩协作
机床测头应用系列二：自动补偿，万千如一
智能搀扶机器人的设计特点是什么
英国电信O2计划今年在英国5G移动频谱拍卖中获得的2.3Ghz频谱
浙江元宇宙政策发布，杭州灵伴科技打造工业AR新引擎
广东潮州引入RFID等技术对古城区进行改造
【树莓派】使用USB网络摄像头替代Raspberry Pi 相机模块