昌平网站开发公司电话,wordpress固定链接404,wordpress 幻灯片标签,传奇世界手游官网目录
1--搜索二叉树
2--完全二叉树
3--平衡二叉树
4--满二叉树 1--搜索二叉树 搜索二叉树的性质#xff1a;左子树的节点值都比根节点小#xff0c;右子树的节点值都比根节点大#xff1b; 如何判断一颗二叉树是搜索二叉树#xff1f; 主要思路#xff1a; 递归自底向…目录
1--搜索二叉树
2--完全二叉树
3--平衡二叉树
4--满二叉树 1--搜索二叉树 搜索二叉树的性质左子树的节点值都比根节点小右子树的节点值都比根节点大 如何判断一颗二叉树是搜索二叉树 主要思路 递归自底向上判断是否是一颗搜索二叉树返回判断结果的同时要返回对应的最小值和最大值 #include iostream
#include climitsstruct TreeNode {int val;TreeNode *left, *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), right(nullptr) {}
};struct ReturnType{bool isBST true;int max 0;int min 0;ReturnType(bool ib, int ma, int mi) : isBST(ib), max(ma), min(mi){}
};class Solution {
public:bool isBST(TreeNode *root){ReturnType res dfs(root);return res.isBST;}ReturnType dfs(TreeNode *root){// 初始化最大值为整型最小值最小值为整型最大值if(root NULL) return ReturnType(true, INT_MIN, INT_MAX); ReturnType left dfs(root-left);ReturnType right dfs(root-right);bool isBST true;if(!left.isBST || !right.isBST || left.max root-val || right.min root-val){isBST false;}int min std::min(std::min(root-val, left.min), std::min(root-val, right.min)); int max std::max(std::max(root-val, left.max), std::max(root-val, right.max));return ReturnType(isBST, max, min);}
};int main(int argc, char *argv[]){TreeNode *Node1 new TreeNode(4);TreeNode *Node2 new TreeNode(2);TreeNode *Node3 new TreeNode(6);TreeNode *Node4 new TreeNode(1);TreeNode *Node5 new TreeNode(3);TreeNode *Node6 new TreeNode(5);TreeNode *Node7 new TreeNode(7);Node1-left Node2;Node1-right Node3;Node2-left Node4;Node2-right Node5;Node3-left Node6;Node3-right Node7;Solution S1;bool res S1.isBST(Node1);if (res) std::cout true std::endl;else std::cout false std::endl;return 0;
}
2--完全二叉树 如何判断一颗二叉树是完全二叉树 主要思路 层次遍历二叉树的节点当遇到第一个节点其左右儿子不双全进行标记往后遇到的所有节点应均为叶子节点当遇到一个不是叶子节点时返回 false 表明二叉树不是完全二叉树 #include iostream
#include queuestruct TreeNode {int val;TreeNode *left, *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), right(nullptr) {}
};class Solution {
public:bool isCBT(TreeNode *root){if(root NULL) return true;std::queueTreeNode* q;q.push(root);bool flag false; while(!q.empty()){ // 层次遍历TreeNode *cur q.front();q.pop();if(cur-left ! NULL) q.push(cur-left);if(cur-right ! NULL) q.push(cur-right);if( // 标记节点后还遇到了不是叶子节点的节点返回false(flag true (cur-left ! NULL || cur-right ! NULL)) || // 左儿子为空右儿子不为空返回false(cur-left NULL cur-right ! NULL)) return false;// 遇到第一个左右儿子不双全的节点进行标记if(cur-left NULL || cur-right NULL) flag true;}return true;}
};int main(int argc, char *argv[]){TreeNode *Node1 new TreeNode(1);TreeNode *Node2 new TreeNode(2);TreeNode *Node3 new TreeNode(3);TreeNode *Node4 new TreeNode(4);TreeNode *Node5 new TreeNode(5);TreeNode *Node6 new TreeNode(6);TreeNode *Node7 new TreeNode(7);TreeNode *Node8 new TreeNode(8);TreeNode *Node9 new TreeNode(9);TreeNode *Node10 new TreeNode(10);TreeNode *Node11 new TreeNode(11);TreeNode *Node12 new TreeNode(12);Node1-left Node2;Node1-right Node3;Node2-left Node4;Node2-right Node5;Node3-left Node6;Node3-right Node7;Node4-left Node8;Node4-right Node9;Node5-left Node10;Node5-right Node11;Node6-left Node12;Solution S1;bool res S1.isCBT(Node1);if (res) std::cout true std::endl;else std::cout false std::endl;return 0;
}
3--平衡二叉树 平衡二叉树要求左子树和右子树的高度差 1 如何判断一颗二叉树是平衡二叉树 主要思路 递归自底向上判断是否是一颗平衡二叉树返回判断结果的同时要返回对应的深度 #include iostream
#include queuestruct TreeNode {int val;TreeNode *left, *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), right(nullptr) {}
};struct ReturnType{bool isbalanced true;int height 0;ReturnType(bool ib, int h) : isbalanced(ib), height(h) {}
};class Solution {
public:bool isBalanced(TreeNode *root){ReturnType res dfs(root);return res.isbalanced;}ReturnType dfs(TreeNode *root){if(root NULL) return ReturnType(true, 0);ReturnType left dfs(root-left);ReturnType right dfs(root-right);int cur_height std::max(left.height, right.height) 1; bool cur_balanced left.isbalanced right.isbalanced std::abs(left.height - right.height) 1;return ReturnType(cur_balanced, cur_height);}private:int height 0;
};int main(int argc, char *argv[]){TreeNode *Node1 new TreeNode(1);TreeNode *Node2 new TreeNode(2);TreeNode *Node3 new TreeNode(3);TreeNode *Node4 new TreeNode(4);TreeNode *Node5 new TreeNode(5);TreeNode *Node6 new TreeNode(6);TreeNode *Node7 new TreeNode(7);TreeNode *Node8 new TreeNode(8);TreeNode *Node9 new TreeNode(9);TreeNode *Node10 new TreeNode(10);TreeNode *Node11 new TreeNode(11);TreeNode *Node12 new TreeNode(12);Node1-left Node2;Node1-right Node3;Node2-left Node4;Node2-right Node5;Node3-left Node6;Node3-right Node7;Node4-left Node8;Node4-right Node9;Node5-left Node10;Node5-right Node11;Node6-left Node12;Solution S1;bool res S1.isBalanced(Node1);if (res) std::cout true std::endl;else std::cout false std::endl;return 0;
}
4--满二叉树 满二叉树的判断节点数 2^深度 - 1 如何判断一颗二叉树是平衡二叉树 主要思路 递归自底向上判断是否是一颗满二叉树返回判断结果的同时要返回对应的深度和节点数 #include iostream
#include queuestruct TreeNode {int val;TreeNode *left, *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), right(nullptr) {}
};struct ReturnType{bool isFCT true;int height 0;int nodes 0;ReturnType(bool ib, int h, int n) : isFCT(ib), height(h), nodes(n){}
};class Solution {
public:bool isFCT(TreeNode *root){ReturnType res dfs(root);return res.isFCT;}ReturnType dfs(TreeNode *root){if(root NULL) return ReturnType(true, 0, 0);ReturnType left dfs(root-left);ReturnType right dfs(root-right);bool isFCT true;int cur_nodes left.nodes right.nodes 1;int cur_height std::max(left.height, right.height) 1;if(!left.isFCT || !right.isFCT || (1cur_height) - 1 ! cur_nodes){isFCT false;}return ReturnType(isFCT, cur_height, cur_nodes);}
};int main(int argc, char *argv[]){TreeNode *Node1 new TreeNode(1);TreeNode *Node2 new TreeNode(2);TreeNode *Node3 new TreeNode(3);TreeNode *Node4 new TreeNode(4);TreeNode *Node5 new TreeNode(5);TreeNode *Node6 new TreeNode(6);TreeNode *Node7 new TreeNode(7);TreeNode *Node8 new TreeNode(8);TreeNode *Node9 new TreeNode(9);TreeNode *Node10 new TreeNode(10);TreeNode *Node11 new TreeNode(11);TreeNode *Node12 new TreeNode(12);Node1-left Node2;Node1-right Node3;Node2-left Node4;Node2-right Node5;Node3-left Node6;Node3-right Node7;Node4-left Node8;Node4-right Node9;Node5-left Node10;Node5-right Node11;Node6-left Node12;Solution S1;bool res S1.isFCT(Node1);if (res) std::cout true std::endl;else std::cout false std::endl;return 0;
}
