//广度优先遍历（层序遍历） -- 借助队列 bfs
void TreeBreadthTraversal(TreeNode* root)
{
    if (root == NULL)
    {
        return;
    }

    //定义一个队列
    deque<TreeNode*> dequeTree;
    dequeTree.push_back(root);  //入队列根节点
    
    //循环队列
    while (dequeTree.size() != 0)
    {
        TreeNode* pTreeNode = dequeTree.front(); //获取队列首元素的值 

        //将该节点的左右节点保存到队列中
        if (pTreeNode->left != NULL) //左
        {
            dequeTree.push_back(pTreeNode->left);
        }

        if (pTreeNode->right != NULL) //右
        {
            dequeTree.push_back(pTreeNode->right);
        }

        //打印当前节点值
        cout << pTreeNode->val << endl;

        //删除第一个节点
        dequeTree.pop_front();
    }
}

//深度遍历 -- 借助栈 dfs
int iTot = 0;
void TreeDepthTraversal(TreeNode* root)
{
    if (root == NULL)
    {
        return;
    }
    int iStart = 0; //开始区间
    int iEnd = 0;  //结束区间 

    //记录当前值所在的区间的开始位置
    iTot += 1;
    iStart = iTot;

    if (root->left != NULL)  //左子树
    {
        TreeDepthTraversal(root->left);
    }

	if (root->right != NULL)  //右子树
	{
		TreeDepthTraversal(root->right);
	}

    //记录当前值所在的区间的结束位置
    iTot += 1;
    iEnd = iTot;

    //打印区间
    printf("%d : [%d, %d] \n", root->val, iStart, iEnd);

    return;
}

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

};