#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct TreeNode{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x):val(x),left(NULL), right(NULL){}
};

int TreeDepth(TreeNode* pRoot){
	int l=0,r=0;
	if(pRoot==NULL) return 0;
	if(pRoot->left!=NULL)
		l=1+TreeDepth(pRoot->left);
	if(pRoot->right!=NULL)
		r=1+TreeDepth(pRoot->right);
	if(l>=r)
		return l;
	else
		return r;
}

void inVist(TreeNode *T,vector<int> &vec,bool &m){
	if(T!=NULL){
		inVist(T->left,vec,m);
		vec.push_back(T->val);
		int l=TreeDepth(T->left);
		int r=TreeDepth(T->right);
		if(abs(l-r)>1)
			m=false;
		inVist(T->right,vec,m);
	}
}

bool IsBalanced_Solution(TreeNode* pRoot){
	if(pRoot==NULL) return false;
	vector<int> vec;
	bool m=true;
	inVist(pRoot,vec,m);
	if(m==false)
		return false;
	else{
		vector<int> temp;
		temp=vec;
		sort(temp.begin(),temp.end());
		int s=vec.size();
		for(int i=0;i<s;i++){
			if(temp[i]!=vec[i])
				return false;
		}
		return true;
	}
}

int main(){
	TreeNode n1(5),n2(3),n3(7),n4(2),n5(4),n6(6);
	TreeNode *root=&n1;
	n1.left=&n2;
	n1.right=&n3;
	n2.left=&n4;
	n2.right=&n5;
	n3.left=&n6;
	cout<<IsBalanced_Solution(root)<<endl;
	system("pause");
}