思想概述
代码如下
//先构建TreeNode结构体
struct TreeNode
{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 根据数组构造二叉树
TreeNode* construct_binary_tree(const vector<int>& vec) {
vector<TreeNode*> vecTree (vec.size(), NULL); //新建一个变量类型为TreeNode*的二叉树数组，一共有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。如果不为空，就被赋予一个新的节点，值为vec[i]
vecTree[i] = node; //一个一个填入新的二叉树数组
if (i == 0) root = node; //根节点单独拉出来，单独赋值
}
// 遍历一遍，根据规则左右孩子赋值就可以了
// 注意这里 结束规则是 i * 2 + 2 < vec.size()，避免空指针(避免越界)
for (int i = 0; i * 2 + 2 < vec.size(); i++) {
if (vecTree[i] != NULL) {
// 线性存储转连式存储关键逻辑
vecTree[i]->left = vecTree[i * 2 + 1];
vecTree[i]->right = vecTree[i * 2 + 2];
}
}
return root;
}
// 层序打印打印二叉树
void print_binary_tree(TreeNode* root) {
queue<TreeNode*> que;//这里采用队列数据结构
if (root != NULL) que.push(root);//先把根节点清空，再把它加入队列
vector<vector<int>> result;
while (!que.empty()) {
int size = que.size();
vector<int> vec;
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
if (node != NULL) {
vec.push_back(node->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<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);
}
这个函数最后返回的指针就是根节点的指针， 这就是 传入二叉树的格式了，也就是力扣上的用例输入格式。
也有不少和我一样的同学在做ACM模式的题目时就经常疑惑：
- 让我传入数值，我会！
- 让我传入数组，我会！
- 让我传入链表，我也会！
- 让我传入二叉树，我懵了，啥？ 传入二叉树？二叉树怎么传？
其实传入二叉树，就是传入二叉树的根节点的指针，和传入链表都是一个逻辑。 这种现象主要就是我对ACM模式过于陌生，说实话，ACM模式才真正的考察代码能力（注意不是算法能力），而力扣的核心代码模式总有一种不够彻底的感觉。 所以，如果我们对ACM模式不够了解，一定要多去练习！
当我完成了二叉树的前中后序遍历之后，这道题就真的过了吗？ 其实并没有。 LeetCode只是用最快的效率让我们返回所需的答案，但二叉树是怎么被打印出来的，我们往往一无所知。 以二叉树的中序遍历为例，我们来写一下ACM模式，看看二叉树是怎么被构建起来的：
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
//先定义结构体
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> stk;
TreeNode* cur = root;
while (cur || !stk.empty()) {
while (cur) {
stk.push(cur);
cur = cur->left;
}
if (!stk.empty()) {
cur = stk.top();
stk.pop();
ans.push_back(cur->val);
cur = cur->right;
}
}
return ans;
}
TreeNode* build(vector<int>& nums) {
if (nums.empty() || nums[0] == -1) return nullptr;
// 将数字转换成 TreeNode
vector<TreeNode*> nodes;
for (int i = 0; i < nums.size(); i++) {
TreeNode* cur = nullptr;
if (nums[i] != -1) cur = new TreeNode(nums[i]);
nodes.push_back(cur);
}
// 父子结点关联，i 的左右孩子下标为 2 * i + 1 和 2 * i + 2
// 由于输入约定是一个满二叉树，所以只要保证最后一个右孩子不越界
for (int i = 0; 2 * i + 2 < nums.size(); i++) {
if (!nodes[i]) continue;
nodes[i]->left = nodes[2 * i + 1];
nodes[i]->right = nodes[2 * i + 2];
}
return nodes[0];
}
int main() {
// 输入序列格式：
// 1. 满二叉树
// 2. 按照层序遍历的顺序
// 3. 空结点用 -1 表示
vector<int> nums = {4,2,5,1,3,-1,6};
TreeNode* root = build(nums);
vector<int> ans = inorderTraversal(root);
for (auto val: ans) {
cout << val << " ";
}
return 0;
}
