21 - 二叉树（三）

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;queue<TreeNode*> 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);}
};