博客

二叉树中的编程问题

#include<iostream>
#include<queue>
#include<list>
#include<string>
#include<unordered_map>
using namespace std;
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode*parent;
	TreeNode() : val(0), left(nullptr), right(nullptr),parent(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr),parent(nullptr) {}
	TreeNode(int x, TreeNode *left, TreeNode *right,TreeNode*parent) : val(x), left(left), right(right),parent(parent) {}
};
//1.树的四种遍历方式                                //在算法课实现的文件上
//2.判断一颗二叉树是否是搜索树                      LeetCode第98题
//3.判断一颗二叉树是否是完全二叉树					
//4.判断一颗二叉树树是否是满二叉树
//5.判断一棵树二叉树是否是平衡二叉树
//6.找到两个节点的最近公共祖先
//7.在二叉树中找到一个节点的后继节点
//8.二叉树的序列化和反序列化

//1.用递归和非递归方式两种方式实现二叉树的先序遍历、中序遍历、后序遍历
//2.如何完成二叉树的宽度优先遍历以及输出最大宽度
//

//1.先序遍历递归(中序、后序只是返回位置不同)与非递归
TreeNode* preorderTree(TreeNode*root)
{
	if (root == NULL)
	{
		return NULL;
	}
	return root;
	preorderTree(root->left);
	preorderTree(root->right);
}
//先序遍历(非递归)压栈
TreeNode*preorderTree(TreeNode*root)
{
	if (root == NULL)
	{
		return NULL;
	}
	stack<TreeNode*> stc;
	stc.push(root);
	while (!stc.empty())
	{
		root = stc.top();
		return stc.top();
		stc.pop();
		if (root->left)
		{
			stc.push(root->left);

		}
		if (root->right)
		{
			stc.push(root->right);
		}
	}
	return NULL;
}
//中序遍历
TreeNode*Inordered(TreeNode*root)
{
	if (root == NULL)
	{
		return NULL;
	}
	stack<TreeNode*> stc;
	while (!stc.empty() || root != NULL)
	{
		if (root != NULL)
		{
			stc.push(root);
			root = root->left;
		}
		else
		{
			return stc.top();
			stc.pop();
			root = root->right;
		}
	}
	return NULL;
}
//后序遍历非递归
TreeNode*posordered(TreeNode* root)
{
	if (root == NULL)
	{
		return NULL;
	}
	stack<TreeNode*>stc1;
	stack<TreeNode*>stc2;
	while (!stc1.empty())
	{
		root = stc1.top();
		stc1.pop();
		stc2.push(root);
		if (root->left != NULL)
		{
			stc1.push(root->left);
		}
		if (root->right != NULL)
		{
			stc1.push(root->right);
		}
	}
	while (!stc2.empty())
	{
		return stc2.top();
		stc2.pop();
	}
}
//2.如何完成二叉树的宽度优先遍历以及输出最大宽度
//宽度优先遍历
TreeNode*widthordered(TreeNode*root)
{
	if (root == NULL)
	{
		return NULL;
	}
	queue<TreeNode*> q;
	q.push(root);
	while (!q.empty())
	{
		root = q.front();
		return q.front();
		q.pop();
		if (root->left)
		{
			q.push(root->left);
		}
		if (root->right)
		{
			q.push(root->right);
		}
	}
	return NULL;
}
//求二叉树的最大宽度(哈希表(O(N))，coding(O(1)))
//哈希表
int maxwidth(TreeNode*root)
{
	queue<TreeNode*> q;
	q.push(root);
	unordered_map<TreeNode*, int>hash;
	hash.emplace(root, 1);
	int curLevel = 1;
	int curLevelNodes = 0;
	int max_ = INT_MIN;
	while (!q.empty())
	{
		TreeNode*cur = q.front();
		q.pop();
		int curNodeLevel = hash.at(cur);
		if (curNodeLevel == curLevel)
		{
			curLevelNodes++;
		}
		else
		{
			max_ = max(max_, curLevelNodes);
			curLevel++;
			curLevelNodes = 1;
		}
		if (cur->left != NULL)
		{
			hash.emplace(cur->left, curNodeLevel + 1);
			q.push(cur->left);
		}
		if (cur->right != NULL)
		{
			hash.emplace(cur->right, curNodeLevel + 1);
			q.push(cur->right);
		}
	}

}

//判断一颗二叉树是否是搜索树
int minval = INT_MIN;
bool isBST(TreeNode*root)
{
	if (root == NULL)
	{
		return true;
	}
	bool isleftBST = isBST(root->left);
	if (!isleftBST)
	{
		return false;
	}
	if (root->val <= minval)
	{
		return false;
	}
	else
	{
		minval = root->val;
	}
	return isBST(root->right);
}
//判断一颗二叉树是否是完全二叉树   如果有右孩子但是没有左孩子则不是完全二叉树
//出现一个单个孩子的节点则以后的节点必是叶节点
bool isCBT(TreeNode*root)
{
	if (root == NULL)
	{
		return true;
	}
	queue<TreeNode*>q;
	TreeNode*l = NULL;
	TreeNode* r = NULL;
	q.push(root);
	bool leaf = false;
	while (!q.empty())
	{
		l = q.front()->left;
		r = q.front()->right;
		q.pop();
		if (leaf && (l!=NULL||r!=NULL)||l==NULL&&r!=NULL)
		{
			return false;
		}
		if (l!=NULL)
		{
			q.push(l);
		}
		if (r!=NULL)
		{
			q.push(r);
		}
		if (l==NULL||r==NULL)
		{
			leaf = true;
		}
	}
	return true;
}
4.判断一颗二叉树是否是满二叉树   利用节点数与最大深度的关系
//或者利用套路
class Info
{
public:
	int height;
	int nodes;
public:
	Info(int h, int n)
	{
		height = h;
		nodes = n;
	}

};
Info process(TreeNode*root)
{
	if (root == NULL)
	{
		return  Info(0, 0);
	}
	Info leftData = process(root->left);
	Info righData = process(root->right);
	int height = max(leftData.height, righData.height) + 1;
	int nodes = leftData.nodes + righData.nodes + 1;
	return Info(height, nodes);
}
bool isFullTree(TreeNode*root)
{
	if (root == NULL)
	{
		return true;
	}
	Info data = process(root);
	return data.nodes == (1 << data.height) - 1;
}


//5.验证是否是平衡二叉树
int height(TreeNode*root)
{
	if (root == NULL)
	{
		return 0;
	}
	return max(height(root->left), height(root->right)) + 1;
}
bool isBlanceTree(TreeNode*root)
{
	if (root == NULL)
	{
		return true;
	}
	return abs(height(root->left) - height(root->right)) <= 1 && isBlanceTree(root->left) && isBlanceTree(root->right);
}
//7.找两个节点的最近公共祖先
TreeNode*loweAncestor(TreeNode*root, TreeNode*r1,TreeNode*r2)
{
	if (root == NULL || root == r1 || root == r2)
	{
		return root;
	}
	TreeNode* left = loweAncestor(root->left,r1,r2);
	TreeNode* right = loweAncestor(root->right,r1,r2);
	if (left != NULL&&right != NULL)
	{
		return root;
	}
	return left != NULL ? left : right;
}
//8.找到后继节点
TreeNode* getLeftMost(TreeNode*root)
{
	if (root == NULL)
	{
		return root;
	}
	while (root->left != NULL)
	{
		root = root->left;
	}
	return root;
}
TreeNode*getsuccessorNode(TreeNode*root)
{
	if (root == NULL)
	{
		return root;
	}
	if (root->right != NULL)
	{
		return getLeftMost(root->right);
	}
	else
	{
		TreeNode* parent = root->parent;
		while (parent != NULL&&parent->left != root)
		{
			root = parent;
			parent = root->parent;
		}
		return parent;
	}
}
//9.二叉树的序列化和反序列化
string serialByPre(TreeNode*root)
{
	if (root == NULL)
	{
		return "#_";
	}
	string res = root->val + "_";
	res += serialByPre(root->left);
	res += serialByPre(root->right);
	return res;
}
TreeNode* rdeserialize(list<string>& dataArray) {
	if (dataArray.front() == "None") {
		dataArray.erase(dataArray.begin());
		return nullptr;
	}

	TreeNode* root = new TreeNode(stoi(dataArray.front()));
	dataArray.erase(dataArray.begin());
	root->left = rdeserialize(dataArray);
	root->right = rdeserialize(dataArray);
	return root;
}

TreeNode* deserialize(string data) {
	list<string> dataArray;
	string str;
	for (auto& ch : data) {
		if (ch == ',') {
			dataArray.push_back(str);
			str.clear();
		}
		else {
			str.push_back(ch);
		}
	}
	if (!str.empty()) {
		dataArray.push_back(str);
		str.clear();
	}
	return rdeserialize(dataArray);
}
int main()
{
	system("pause");
	return 0;
}