三、完全二叉树的节点个数
--1、题目链接：Leedcode--222完全二叉树的节点个数
--2、节点个数：
（1）递归法：
class Solution { public: int countNodes(TreeNode root) { if(root == nullptr) return 0; //我们可以利用满二叉树求节点数量的公式结合递归来求解完全二叉树的节点个数 //首先设置两个指针--左指针和右指针来检查当前树的最左边和最右边的高度是否相等，若相等则是满二叉树，我们不需要担心树的边的中间有空节点，因为题目中已经规定这棵树是完全二叉树，这就表明树两条边界的中间一定没有空节点 TreeNode *left = root->left; TreeNode *right = root->right; int leftDepth = 1; int rightDepth = 1; while(left != nullptr) { left = left->left; leftDepth++; } while(right != nullptr) { right = right->right; rightDepth++; } if(leftDepth == rightDepth) return (1<<leftDepth) - 1; //位运算大法好，一层层将结果向上传递 int leftTreeNum = countNodes(root->left); int rightTreeNum = countNodes(root->right); return leftTreeNum + rightTreeNum + 1; } };
在递归法中，我们用到了一个已知的常识：满二叉树的节点数量 = 2^满二叉树的深度次方 - 1。
什么是完全二叉树
什么是满二叉树
我们不难发现完全二叉树其实就是由一个个的满二叉树构成的。
这里的递归其实就是树的上层开始搜索是否有满二叉树，有则直接通过求满二叉树的节点公式就可以直接求出一大片的节点数量，省去了一大部分的遍历，这就是这个递归的方法要优于迭代法的原因所在。我们不需要担心判断这棵树是否是满二叉树时，数的最左右两侧的树枝长度相等但是中间可能不相等，其实我们完全没有必要来担心这个问题，因为题中交代给出的是一颗完全二叉树，是不会出现两边等中间不等的情况的。
（2）迭代法：--暴力计算节点个数，直接遍历所有节点
class Solution { public: //题目中已经给出了一颗完全二叉树，我们就不需要自己去判断这棵树是否是完全二叉树了 int countNodes(TreeNode root) { if(root == nullptr) return 0; queue<TreeNode*>que; if(root != nullptr) que.push(root); int count = 0; //用来统计节点的数量 while(!que.empty()) { int size = que.size(); count += size; while(size--) { TreeNode *cur = que.front(); que.pop(); if(cur->left != nullptr) que.push(cur->left); if(cur->right != nullptr) que.push(cur->right); } } return count; }
四、平衡二叉树
--1、平衡二叉树的定义：
一颗平衡二叉树的定义是：一个节点的左右子树的高度差的绝对值不超过1。
--2、题目链接：Leedcode--110平衡二叉树
--3、解题方法：
（1）递归法：
class Solution { public: int judgeTreeBalance(TreeNode* root) { if(root == nullptr) return 0; int leftHeight = judgeTreeBalance(root->left); if(leftHeight == -1) return -1; int rightHeight = judgeTreeBalance(root->right); if(rightHeight == -1) return -1; if(abs(leftHeight - rightHeight) > 1) return -1; else return max(leftHeight, rightHeight) + 1; } bool isBalanced(TreeNode* root) { if(root == nullptr) return true; return judgeTreeBalance(root) == -1 ? false : true; } };
我们用-1作为这棵树不是平衡二叉树的信标，若节点收到子节点传回的-1，则继续将-1这个信号继续传给它的父节点，直至传到首节点。若函数返回-1，则我们可以断定，这棵树不是一颗平衡二叉树。
（2）迭代法：
暴力判断：
从上至下遍历每个节点，只要发现不匹配的节点立即返回false报错。
class Solution { public: int nodeHeight(TreeNode* cur) { if(cur == nullptr) return 0; int leftHeight = nodeHeight(cur->left); int rightHeight = nodeHeight(cur->right); return 1 + max(leftHeight, rightHeight); } bool isBalanced(TreeNode* root) { if(root == nullptr) return true; queue<TreeNode*>que; que.push(root); while(!que.empty()) { int size = que.size(); while(size--) { TreeNode *node = que.front(); que.pop(); if(abs(nodeHeight(node->left) - nodeHeight(node->right)) > 1) return false; if(node->left != nullptr) que.push(node->left); if(node->right != nullptr) que.push(node->right); } } return true; } };
