#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 包含：根据数组构造二叉树、前中后序遍历、求树的深度、销毁树
// https://programmercarl.com/%E5%89%8D%E5%BA%8F/ACM%E6%A8%A1%E5%BC%8F%E5%A6%82%E4%BD%95%E6%9E%84%E5%BB%BA%E4%BA%8C%E5%8F%89%E6%A0%91.html

typedef struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
}TreeNode,*Treelink;


// 根据数组构造二叉树
TreeNode* construct_binary_tree(const vector<int>& vec) {
    vector<TreeNode*> 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 < vec.size(); i++) {
        if (vecTree[i] != NULL) {
            vecTree[i]->left = vecTree[i * 2 + 1];
            vecTree[i]->right = vecTree[i * 2 + 2];
        }
    }
    return root;
}

// 获取深度
/* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */
int BiTreeDepth(TreeNode* T)
{
	int i,j;
	if(!T)
		return 0;
	if(T->left)
		i=BiTreeDepth(T->left);
	else
		i=0;
	if(T->right)
		j=BiTreeDepth(T->right);
	else
		j=0;
	return i>j?i+1:j+1;
}
// 最大深度
// class Solution {
// public:
//     int maxLevel = 0;
//     int maxDepth(TreeNode* root) {
//         if (!root) return 0;
//         int left = maxDepth(root->left);
//         int right = maxDepth(root->right);
//         return max(left, right) + 1;
//     }
// };


/* 初始条件: 二叉树T存在。操作结果: 销毁二叉树T */
void DestroyBiTree(TreeNode *T)
{ 
	if(T!=nullptr) 
	{
		if(T->left) /* 有左孩子 */
			DestroyBiTree(T->left); /* 销毁左孩子子树 */
		if(T->right) /* 有右孩子 */
			DestroyBiTree(T->right); /* 销毁右孩子子树 */
		delete T; /* 释放根结点 */
		T = nullptr; /* 空指针赋0 */
	}
}

// 层序打印打印二叉树
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;
    }
}


/* 初始条件: 二叉树T存在 */
/* 操作结果: 前序递归遍历T */
void PreOrderTraverse(TreeNode* T)
{ 
	if(T==NULL)
		return;
	printf("%d",T->val);/* 显示结点数据，可以更改为其它对结点操作 */
	PreOrderTraverse(T->left); /* 再先序遍历左子树 */
	PreOrderTraverse(T->right); /* 最后先序遍历右子树 */
}

/* 初始条件: 二叉树T存在 */
/* 操作结果: 中序递归遍历T */
void InOrderTraverse(TreeNode* T)
{ 
	if(T==NULL)
		return;
	InOrderTraverse(T->left); /* 中序遍历左子树 */
	printf("%d",T->val);/* 显示结点数据，可以更改为其它对结点操作 */
	InOrderTraverse(T->right); /* 最后中序遍历右子树 */
}

/* 初始条件: 二叉树T存在 */
/* 操作结果: 后序递归遍历T */
void PostOrderTraverse(TreeNode* T)
{
	if(T==NULL)
		return;
	PostOrderTraverse(T->left); /* 先后序遍历左子树  */
	PostOrderTraverse(T->right); /* 再后序遍历右子树  */
	printf("%d",T->val);/* 显示结点数据，可以更改为其它对结点操作 */
}


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);

    cout << "========前序(根左右)========" << endl;
    PreOrderTraverse(root);
    cout << endl;
    cout << "========中序（左根右）========" << endl;
    InOrderTraverse(root);
    cout << endl;
    cout << "========后序（左右根）========" << endl;
    PostOrderTraverse(root);
    cout << endl;

    cout << "树的深度为：" << BiTreeDepth(root) << endl;
    
    cout << "销毁" << endl;
    DestroyBiTree(root);

}