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

//先序遍历数组
//输入：root = [1,null,2,3]
//输出：[1,3,2]
//输入：root = [1,null,2]
//输出：[1,2]
/*
 1
  \
  2
  /
3
*/

//层序遍历数组
//    3
//   / \
//  9  20
//    /  \
//   15   7
//inout : [3,9,20,null,null,15,7]
//vector<int> level_vecs = {3,9,20,-1,-1,15,7};

void CreatBinaryTreeByPreVec(const vector<int>& vec, TreeNode* &cur, int index)
{
    if (index < vec.size() && vec[index] != -1)//不能越界
    {
        cur = new TreeNode(vec[index]);
        cout << "cur: " << cur->val << endl;
        CreatBinaryTreeByPreVec(vec, cur->left, ++index);
        CreatBinaryTreeByPreVec(vec, cur->right, ++index);
    }
}

void CreatBinaryTreeByLevelVec(const vector<int>& vec, TreeNode* &cur, int index)
{
    if (index < vec.size() && vec[index] != -1) {
        cur = new TreeNode(vec[index]);
        CreatBinaryTreeByLevelVec(vec, cur->left, 2*index+1);
        if (2*index+2 < vec.size()) {
            CreatBinaryTreeByLevelVec(vec, cur->right, 2*index+2);
        }
    }
}

void inOrder(TreeNode *root, vector<int> &res) {
    if (!root) return;
    if (root->left) {
        inOrder(root->left, res);
    }
    res.push_back(root->val);
    if (root->right) {
        inOrder(root->right, res);
    }
}

void postOrder(TreeNode *root, vector<int> &res) {
    if (!root) return;
    if (root->left) {
        postOrder(root->left, res);
    }
    if (root->right) {
        postOrder(root->right, res);
    }
    res.push_back(root->val);
}


void preOrder(TreeNode *root, vector<int> &res) {
    if (!root) return;
    res.push_back(root->val);
    if (root->left) {
        preOrder(root->left, res);
    }
    if (root->right) {
        preOrder(root->right, res);
    }
}

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    inOrder(root, res);
    return res;
}

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    preOrder(root, res);
    return res;
}

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    postOrder(root, res);
    return res;
}

//    3
//   / \
//  9  20
//    /  \
//   15   7
//inout : [3,9,20,null,null,15,7]
//vector<int> level_vecs = {3,9,20,-1,-1,15,7};

vector<vector<int>> levelOrder(TreeNode* root) {
    //迭代
    //广度优先搜索(BFS队列)
    vector<vector<int>> res;
    if (!root)
        return res;
    queue<TreeNode*> q;
    q.push(root);

    while(!q.empty()) {
        res.emplace_back();
        int len = q.size();
        for (int i = 0; i < len; i++) {
            TreeNode* node = q.front();
            res.back().push_back(node->val);
            q.pop();

            if (node->left) {
               q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
    }
    return res;
}

vector<vector<int>> levelOrderBottom(TreeNode* root) {
    vector<vector<int>> res;
    if (!root)
        return res;
    queue<TreeNode*> q;
    q.push(root);

    while(!q.empty()) {
        res.emplace_back();
        int len = q.size();
        for (int i = 0; i < len; i++) {
            TreeNode* node = q.front();
            res.back().push_back(node->val);
            q.pop();

            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
    }
    reverse(res.begin(), res.end());
    return res;
}

void PrintFromTopToBottom(TreeNode* pRoot)
{
    //层序打印队列
    if(pRoot == nullptr)
        return;

    deque<TreeNode *> dequeTreeNode;

    dequeTreeNode.push_back(pRoot);
    while(dequeTreeNode.size())
    {
        TreeNode *pNode = dequeTreeNode.front();
        dequeTreeNode.pop_front();
        cout<< pNode->val << " ";
        if(pNode->left)
            dequeTreeNode.push_back(pNode->left);

        if(pNode->right)
            dequeTreeNode.push_back(pNode->right);
    }
    cout << endl;
}