二叉树

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};
*/
class Solution {
public:
	TreeLinkNode* GetNext(TreeLinkNode* pNode)
	{
		if (pNode == NULL)return NULL;
		TreeLinkNode*temp=NULL,*temp1=NULL;
		if (pNode->right != NULL)
		{
			temp = pNode->right;

			while (temp->left != NULL)
			{
				temp = temp->left;
			}
			return temp;
		}
		else if(pNode->next!=NULL)//因为给的可能是根节点，所以这里要判断下。
		{

			temp= pNode->next,temp1 = pNode;
			while (temp != NULL&&temp->left != temp1)//注意判断条件
			{
				temp1 = temp;
				temp = temp->next;
			}

		}

		return temp;
	}
};

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
	bool isSymmetrical(TreeNode* pRoot)
	{
		if (pRoot == NULL)return true;
		return symmetrical(pRoot->left,pRoot->right);
	}
	bool symmetrical(TreeNode*left, TreeNode*right)
	{
		if ((!left) && (!right)) return true;
		if (!(left)||!(right))return false;
		return (left->val == right->val) && (symmetrical(left->left, right->right) && symmetrical(left->right, right->left));
	}//左子树的左子树个右子树的右子树对称；左子树的右子树和右子树的左子树对称；

};

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
	vector<vector<int> > Print(TreeNode* pRoot) {

		int depth = 0;

		vector<vector<int> > result;
		if (pRoot == NULL)return result;
		vector<TreeNode*>a;
		a.push_back(pRoot);
		print_level(a, depth, result);
		return result;
	}
	void print_level(vector<TreeNode*>a,int depth, vector<vector<int> >&result)
	{
		if (a.size() == 0)return;
		vector<int>level;
		vector<TreeNode*> temp;
		if (depth % 2 == 0)
		{
			for (int i = 0; i < a.size(); i++)
			{
				level.push_back(a[i]->val);//从前往后打印
                //用新的vector<TreeNode*> temp来存下一层的指针
				if (a[i]->left != NULL)temp.push_back(a[i]->left);
				if (a[i]->right != NULL)temp.push_back(a[i]->right);
			}
		}
		else
		{
			for (int i = a.size()-1; i>=0; i--)//从后往前打印
			{
				level.push_back(a[i]->val);
			}
			for (int i = 0; i < a.size(); i++)//用新的vector<TreeNode*> temp来存下一层的指针
			{

				if (a[i]->left != NULL)temp.push_back(a[i]->left);
				if (a[i]->right != NULL)temp.push_back(a[i]->right);
			}
		}
		depth++;
		result.push_back(level);//打印当前层结果
		print_level(temp,depth,result);//迭代调用
	}
};

	char* Serialize(TreeNode *root) {
		if (root == NULL)return NULL;
		string str;
		getSerialize(root, str);
		char *ret = new char[str.length() + 1];
		int i;
		for (i = 0; i < str.length(); i++) {
			ret[i] = str[i];
		}
		ret[i] = '\0';
		return ret;
		//char*a= (char*)str.c_str() ;
		//return a;
	}

	void  getSerialize(TreeNode*root, string& str)
	{
		if (root == NULL)
		{
			str += '#';
			return;
		}
		str += to_string(root->val);
		str += ',';
		getSerialize(root->left, str);
		getSerialize(root->right, str);

	}

		TreeNode* Deserialize(char *str) {
		if (str == NULL)
			return NULL;
		TreeNode *ret = Deserialize(&str);

		return ret;
	}
	TreeNode* Deserialize(char **str) {
		TreeNode*root;
		if (**str == '#') {
			++(*str);
			return NULL;
		}
		int num = 0;
		while ((**str)!='\0'&&(**str)!=',')
		{
			num = num * 10 + ((**str) - '0');
			++(*str);
		}
		root = new TreeNode(num);
		if (**str == '\0')return root;
		++(*str);
		root->left = Deserialize(str);
		root->right = Deserialize(str);
		return root;
	}

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
	TreeNode* KthNode(TreeNode* pRoot, int k)
	{
        
		if (pRoot == NULL||k<1)return NULL;//边界
		vector<TreeNode*>a;
		midNode(pRoot, a);
		if (k >a.size())return NULL;//边界
		return a[k-1];
	}
	void midNode(TreeNode*p, vector<TreeNode*>&a)
	{
		if (p == NULL)return;
		midNode(p->left, a);
		a.push_back(p);
		midNode(p->right, a);
	}

    
};

	priority_queue<int, vector<int>, less<int> > p;
	priority_queue<int, vector<int>, greater<int> > q;
	void Insert(int num) {
		if (p.empty() || num <= p.top()) p.push(num);//如果是奇数个的话，p要比q多一个元素
		else q.push(num);
		if (p.size() == q.size() + 2) q.push(p.top()), p.pop();//保持两个堆的数据个数最多差一个，p.top()返回的是最大值，因为是<操作符，越大的优先级越高
		if (p.size() + 1 == q.size()) p.push(q.top()), q.pop();//q.top()返回的是最小值，越小的优先级越高
	}
	double GetMedian() {
		return p.size() == q.size() ? (p.top() + q.top()) / 2.0 : p.top();
	}