二叉树中的编程问题
#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;
}
版权声明:本文为qq_46897935原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。