网站续费问题,网站内容建设ppt,宝塔面板建设网站,沧州网站建设公司电话文章目录1. 二叉树的镜像2. 判断是不是完全二叉树3. 完全二叉树的节点个数4. 判断是不是平衡二叉树1. 二叉树的镜像 #include ctime
class Solution {public:TreeNode* Mirror(TreeNode* pRoot) {// write code hereif (pRoot nullptr) return pRoot;//这里记得要记得…
文章目录1. 二叉树的镜像2. 判断是不是完全二叉树3. 完全二叉树的节点个数4. 判断是不是平衡二叉树1. 二叉树的镜像 #include ctime
class Solution {public:TreeNode* Mirror(TreeNode* pRoot) {// write code hereif (pRoot nullptr) return pRoot;//这里记得要记得保存pRoot-left否则就会被pRoot-right覆盖TreeNode* node pRoot-left;pRoot-left Mirror(pRoot-right);pRoot-right Mirror(node);return pRoot;}
};2. 判断是不是完全二叉树 先判断空树一定是完全二叉树。初始化一个队列辅助层次遍历将根节点加入。逐渐从队列中弹出元素访问节点如果遇到某个节点为空进行标记代表到了完全二叉树的最下层若是后续还有访问则说明提前出现了叶子节点不符合完全二叉树的性质。否则继续加入左右子节点进入队列排队等待访问。
/*** struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {public:bool isCompleteTree(TreeNode* root) {// write code hereif (root nullptr) return true;queueTreeNode* que;que.push(root);bool flag false;while (!que.empty()) {int size que.size();for (int i 0; i size; i) {TreeNode* node que.front();que.pop();if(node nullptr){flag true;}else{if(flag) return false;que.push(node-left);que.push(node-right);}}}return true;}
};3. 完全二叉树的节点个数 在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层则该层包含 1~ 2^(h-1) 个节点。
完全二叉树只有两种情况
情况一就是满二叉树可以直接用 2^树深度 - 1 来计算注意这里根节点深度为1。情况二最后一层叶子节点没有满分别递归左孩子和右孩子递归到某一深度一定会有左孩子或者右孩子为满二叉树然后依然可以按照情况1来计算。
class Solution {
public:int countNodes(TreeNode* root) {if(root nullptr){return 0;}TreeNode* left root-left;TreeNode* right root-right;int leftd 0;int rightd 0;while(left ! nullptr){left left-left;leftd;}while(right ! nullptr){right right-right;rightd;}if(leftd rightd){return (2 leftd) - 1;}return countNodes(root-left) countNodes(root-right) 1;}
};4. 判断是不是平衡二叉树 分别求出其左右子树的高度然后如果差值小于等于1则返回当前二叉树的高度否则返回-1表示已经不是二叉平衡树了。
class Solution {
public:bool IsBalanced_Solution(TreeNode* pRoot) {if(pRoot nullptr) return true;int result getHigh(pRoot);return result -1 ? false : true;}
private:int getHigh(TreeNode* root){if(root nullptr) return 0;int left getHigh(root-left);if(left -1) return -1;int right getHigh(root-right);if(right -1) return -1;return abs(left - right) 1 ? -1 : 1 max(left, right);}
};
