目录
222.完全二叉树的节点个数
题目
代码（层序迭代）
代码（后序递归）
代码（满二次树递归）
总结
110.平衡二叉树
题目
代码（后序递归）
代码（层序迭代）
代码（前序迭代）
总结
222.完全二叉树的节点个数
题目
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例 1：
输入：root = [1,2,3,4,5,6] 输出：6
代码（层序迭代）
class Solution {
public int countNodes(TreeNode root) {
//用层序迭代递归计算
int size = 0; //初始大小为0
Queue<TreeNode> que = new ArrayDeque<>();
if(root == null){
return 0;
}
que.offer(root);
while(!que.isEmpty()){
int len = que.size(); //获取当前层的节点个数
size += len; //更新size
//当前层节点一个个出队
while(len-- > 0){
TreeNode cur = que.poll();
//处理左右孩子，进队
if(cur.left != null){
que.offer(cur.left);
}
if(cur.right != null){
que.offer(cur.right);
}
}
}
return size;
}
}代码（后序递归）
class Solution {
public int countNodes(TreeNode root) {
//用后序递归遍历计算
//终止条件
if(root == null){
return 0;
}
//单层逻辑
int left = countNodes(root.left); //计算左子树节点数量（左）
int right = countNodes(root.right); //计算右子树节点数量（右）
int result = left + right + 1; //中
return result;
}
}代码（满二次树递归最难理解）
class Solution {
//用完全二叉树的性质递归计算，时间复杂度小于o(n)
//核心原理是如果是满二叉树，左右侧深度一样,可以2^depth-1直接计算，不用全部遍历
public int countNodes(TreeNode root) {
//终止条件1
if(root == null){
return 0;
}
//终止条件2，是满二叉树，可以直接根据深度计算节点数
TreeNode left = root.left;
TreeNode right = root.right;
int leftdepth = 0;
int rightdepth = 0;
//左孩子一直往左下走，计算左下深度
while(left != null){
left = left.left;
leftdepth++;
}
//右孩子一直往右下走，计算右下深度
while(right != null){
right = right.right;
rightdepth++;
}
//如果左右深度一样，说明是满二叉树，直接计算返回
if(leftdepth == rightdepth){
//按注释计算2^depth-1 力扣上不知道为什么通不过
//return ((int)Math.pow(2,leftdepth) - 1);
return (2 << leftdepth) - 1;
}
//单层逻辑
int l = countNodes(root.left); //计算左孩子节点数（左）
int r = countNodes(root.right); //计算右孩子节点数（右）
int result = l + r + 1; //中
return result;
}
}总结
层序迭代和后序递归的核心逻辑很简单，就是用普通的遍历二叉树的方法，一边遍历一边计算节点数，即在原先的遍历代码中加上计算节点数的代码即可。时间复杂度是o(n)。
满二叉树递归的核心逻辑，利用了满二叉树的性质，如果一个子树的满二叉树，从根节点往左和往右的最大深度是一样的。因此我们通过前序递归遍历二叉树，如果当前节点时满二叉树（终止条件），就可以直接计算节点数是2^depth-1，不用继续遍历其孩子节点。如果不是满二叉树（单层逻辑），就继续前序遍历下去，不是满二叉树的节点数=左子树节点+右子树节点+1。时间复杂度<=o(n)。
110.平衡二叉树
题目
给定一个二叉树，判断它是否是平衡二叉树
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：true
代码（后序递归最难理解）
class Solution {
//后序递归判断
public boolean isBalanced(TreeNode root) {
int result = postOrder(root);
if(result == -1){
return false;
}
else{
return true;
}
}
//后序遍历，判断每个节点是否满足高度差<=1
//返回值int有两层意思：如果=-1代表当前节点不平衡，如果不是-1，代表当前节点的高度
public int postOrder(TreeNode root){
//终止条件1
if(root == null){
return 0;
}
//计算当前节点的左右孩子高度
int leftheight = postOrder(root.left); //左子树高度
int rightheight = postOrder(root.right); //右子树高度
//终止条件2，左子树不平衡
if(leftheight == -1){
return -1;
}
//终止条件3，右子树不平衡
if(rightheight == -1){
return -1;
}
//终止条件4,左右子树高度差大于1
if(Math.abs(leftheight - rightheight) > 1){
return -1;
}
//单层循环
//如果该节点满足平衡二叉条件，计算该节点的高度，继续递归判断
int result = 1 + Math.max(leftheight,rightheight);
return result;
}
}代码（层序迭代）
class Solution {
//层序迭代判断，核心逻辑是层序遍历每个节点，判断是否满足平衡条件
public boolean isBalanced(TreeNode root) {
//层序遍历节点，逐个判断该节点是否满足高度差<=1
Queue<TreeNode> que = new ArrayDeque<>();
if(root == null){
return true;
}
que.offer(root);
while(!que.isEmpty()){
int size = que.size();
//处理当前层的所有节点
while(size-- > 0){
TreeNode cur = que.poll();
//计算cur的左右孩子的高度
int leftheight = getheight(cur.left);
int rightheight = getheight(cur.right);
//如果高度差>1，不满足平衡直接return
if(Math.abs(leftheight - rightheight) > 1){
return false;
}
if(cur.left != null){
que.offer(cur.left);
}
if(cur.right != null){
que.offer(cur.right);
}
}
}
return true;
}
//计算cur节点的高度
public int getheight(TreeNode cur){
//终止条件
if(cur == null){
return 0;
}
//单层逻辑
int left = getheight(cur.left);
int right = getheight(cur.right);
return 1 + Math.max(left,right);
}
}代码（前序迭代）
class Solution {
public boolean isBalanced(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
if(root == null){
return true;
}
//前序迭代遍历每一个节点，并判断该节点是否平衡
stack.push(root);
while(!stack.isEmpty()){
TreeNode cur = stack.pop();
//计算当前cur节点的左右高度
int leftheight = getheight(cur.left);
int rightheight = getheight(cur.right);
//如果cur不平衡，直接返回false
if(Math.abs(leftheight - rightheight) > 1){
return false;
}
if(cur.right != null){
stack.push(cur.right);
}
if(cur.left != null){
stack.push(cur.left);
}
}
//遍历完全部节点，都满足平衡，就返回true
return true;
}
//计算cur节点的高度
public int getheight(TreeNode cur){
//终止条件
if(cur == null){
return 0;
}
//单层逻辑
int left = getheight(cur.left);
int right = getheight(cur.right);
return 1 + Math.max(left,right);
}
}总结
迭代法的逻辑很简单，就是用前序、层序遍历每一个节点时，同时计算当前节点的左右孩子高度，判断当前节点的高度差是否满足平衡，如果不满足，直接返回false，如果当前节点满足，再迭代判断后面的节点。最后，如果所有节点遍历完，都没有返回false，说明二叉树的每一个节点都满足平衡条件，就返回true。
递归法，核心逻辑是一边后序递归二叉树，一边计算当前节点的左右孩子高度，判断当前遍历节点是否满足平衡，如果不满足平衡就返回-1，如果满足平衡就计算当前节点的高度。
递归法有四个终止条件，一是节点为null，返回0。二是节点的左右高度差>1，返回-1。还有两种情况千万不能漏，如果该节点的左孩子or右孩子的返回值=-1，说明其左孩子or右孩子已经不平衡了，直接返回-1。
