★★★★★ 二叉树遍历 前序 中序 后序 DFS BFS 树的最大深度，最小深度

//二叉链表表示的二叉树结构定义
struct TreeNode {
	int val;//该节点的值
	struct TreeNode *left;//左孩子
	struct TreeNode *right;//右孩子
	TreeNode(int x) :
		val(x), left(NULL), right(NULL) {
	}
};

/** 构建的树的结构如下： *代表空
          5
     4		  9
  2   *		7   *
1   3     6   8

#先序遍历：5 4 2 1 3 9 7 6 8
中序遍历：1 2 3 4 5 6 7 8 9
后序遍历：1 3 2 4 6 8 7 9 5
*/

//先序遍历   递归
void PreOrderTraverse(TreeNode* root,vector<int> &path)
{
	if (root != NULL)
	{
		//cout << root->val << " ";//先显示根节点的数值，可改为对节点的其他操作
		//逻辑处理
		path.push_back(root->val);
		PreOrderTraverse(root->left,path);//再遍历左子树
		PreOrderTraverse(root->right,path);//最后遍历右子树
	}
}



//中序遍历   递归  左根右
void InOrderTraverse(TreeNode* root, vector<int> &path)
{
	if (root != NULL)
	{
		InOrderTraverse(root->left,path);//先遍历左子树
		//cout << root->val << " ";//再显示根节点的数值，可改为对节点的其他操作
		//逻辑处理
		path.push_back(root->val);
		InOrderTraverse(root->right,path);//最后遍历右子树
	}
}


//后序遍历   递归  左右根
void PostTraverse(TreeNode* root, vector<int> &path)
{
	if (root != NULL)
	{
		PostTraverse(root->left,path);//先遍历左子树
		PostTraverse(root->right,path);//在遍历右子树
		//cout << root->val << " ";//最后显示根节点的数值，可改为对节点的其他操作
		//逻辑处理
		path.push_back(root->val);
	}
}
      非递归实现
//pair是一种模板类型，其中包含两个数据值，两个数据的类型可以不同，基本的定义如下：
 //pair<int, string> a;
//表示a中有两个类型，第一个元素是int型的，第二个元素是string类型的，
//如果创建pair的时候没有对其进行初始化，则调用默认构造函数对其初始化。

//使用make_pair对已存在的两个数据构造一个新的pair类型
void preorderTraversalNew(TreeNode* root, vector<int> &path)
{
	stack < pair<TreeNode* ,bool> > m_stack;
	m_stack.push(make_pair(root,false));
	bool visited;
	
	while (!m_stack.empty())
	{
		//对于pair类，由于它只有两个元素，分别名为first和second，
		root = m_stack.top().first;////因此直接使用普通的点操作符即可访问其成员
		visited = m_stack.top().second;
		m_stack.pop();
		
		if (root == NULL)
			continue;
		if (visited)
		{
			//逻辑处理
			path.push_back(root->val);
		}
		else
		{
			m_stack.push(make_pair(root->right,false));
			m_stack.push(make_pair(root->left, false));
			m_stack.push(make_pair(root, true));
		}
	}
}

// 更简单的非递归中序遍历
void inorderTraversalNew(TreeNode *root, vector<int> &path)
{
	stack< pair<TreeNode *, bool> > s;
	s.push(make_pair(root, false));
	bool visited;
	while (!s.empty())
	{
		root = s.top().first;
		visited = s.top().second;
		s.pop();
		if (root == NULL)
			continue;
		if (visited)
		{
			path.push_back(root->val);
		}
		else
		{
			s.push(make_pair(root->right, false));
			s.push(make_pair(root, true));
			s.push(make_pair(root->left, false));
		}
	}
}




//更简单的非递归后序遍历
void postorderTraversalNew(TreeNode *root, vector<int> &path)
{
	stack< pair<TreeNode *, bool> > s;
	s.push(make_pair(root, false));
	bool visited;
	while (!s.empty())
	{
		root = s.top().first;
		visited = s.top().second;
		s.pop();
		if (root == NULL)
			continue;
		if (visited)
		{
			path.push_back(root->val);
		}
		else
		{
			s.push(make_pair(root, true));
			s.push(make_pair(root->right, false));
			s.push(make_pair(root->left, false));
		}
	}
}


//用queue实现的BFS
//借助队列数据结构，由于队列是先进先出的顺序，因此可以先将左子树入队，然后再将右子树入队。
//这样一来，左子树结点就存在队头，可以先被访问到。
void BFS(TreeNode *root, vector<int> &path)
{
	if (root == NULL)
		return;
	queue<TreeNode *> que;
	que.push(root);

	while (!que.empty())
	{
		TreeNode* node = que.front();//首元素
		path.push_back(node->val);
		if (node->left != NULL)
			que.push(node->left);
		if (node->right != NULL)
			que.push(node->right);
		que.pop();
	}

}

// DFS的迭代实现版本（stack）  
void DFS(TreeNode *root, vector<int> &path)
{
	if (root == NULL)
		return;
	stack<TreeNode*> m_stack;
	m_stack.push(root);

	while (!m_stack.empty())
	{
		TreeNode *node = m_stack.top();
		path.push_back(node->val);
		
		m_stack.pop();
		if (node->right != NULL)
			m_stack.push(node->right);
		if (node->left != NULL)
			m_stack.push(node->left);
	}

}

//DFS的递归
void DFS_Recursive(TreeNode* root, vector<int> &path)
{
	if (root == NULL)
		return;
	path.push_back(root->val);
	if (root->left != NULL)
		DFS_Recursive(root->left,path);
	if (root->right != NULL)
		DFS_Recursive(root->right,path);
}


int getDepth(TreeNode * root)
{
	if (root == NULL)
		return 0;
	int leftDepth = getDepth(root->left);
	int rightDepth = getDepth(root->right);

	return 1 + max(leftDepth, rightDepth);
}

int getminDepth(TreeNode *root) {
	if (root == NULL)
		return 0;
	int left = getminDepth(root->left);
	int right = getminDepth(root->right);
	if (left == 0 || right == 0)
		return 1 + left + right;
	return 1 + min(left, right);
}

bool IsBlancedTree(TreeNode* root)
{
	if (root == nullptr)
		return true;
	int leftDepth = getDepth(root->left);
	int rightDepth = getDepth(root->right);

	if (abs(leftDepth - rightDepth) > 1)
		return false;

	return IsBlancedTree(root->left)&&IsBlancedTree(root->right);
}

int main()
{

	TreeNode* head = buildTree();
	vector<int> res;
	cout << "先序遍历" << endl;
	PreOrderTraverse(head,res);
	for (int i = 0; i < res.size(); i++)
		cout << res[i] << " ";
	cout << endl;
	res.clear();

	PreOrderRecursion(head,res);
	for (int i = 0; i < res.size(); i++)
		cout << res[i] << " ";
	cout << endl;
	res.clear();

	preorderTraversalNew(head,res);
	for (int i = 0; i < res.size(); i++)
		cout << res[i] << " ";
	cout << endl;
	res.clear();

	cout << "中序遍历" << endl;
	InOrderTraverse(head, res);
	for (int i = 0; i < res.size(); i++)
		cout << res[i] << " ";
	cout << endl;
	res.clear();

	InOrderRecursion(head, res);
	for (int i = 0; i < res.size(); i++)
		cout << res[i] << " ";
	cout << endl;
	res.clear();

	inorderTraversalNew(head,res);
	for (int i = 0; i < res.size(); i++)
		cout << res[i] << " ";
	cout << endl;
	res.clear();

	cout << "后序遍历" << endl;
	PostTraverse(head,res);
	for (int i = 0; i < res.size(); i++)
		cout << res[i] << " ";
	cout << endl;
	res.clear();

	PostRecursion(head,res);
	for (int i = 0; i < res.size(); i++)
		cout << res[i] << " ";
	cout << endl;
	res.clear();

	postorderTraversalNew(head,res);
	for (int i = 0; i < res.size(); i++)
		cout << res[i] << " ";
	cout << endl;
	res.clear();


	cout << "BFS" << endl;
	BFS(head,res);
	for (int i = 0; i < res.size(); i++)
		cout << res[i] << " ";
	cout << endl;
	res.clear();

	cout << "DFS" << endl;
	DFS(head,res);
	for (int i = 0; i < res.size(); i++)
		cout << res[i] << " ";
	cout << endl;
	res.clear();

	cout << "树的最大深度" << getDepth(head)<<endl;
	cout << "该树的最小深度" << getminDepth(head) << endl;

	cout << "是否是平衡树" << IsBlancedTree(head) << endl;


	system("pause");

	return 0;
}