110.平衡二叉树（后序）
题目链接 | 文档讲解 |视频讲解 : 链接
平衡二叉树：每个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1
1.思路：
采用后序遍历，首先需要计算左右子树的高度，然后判断左右子树的高度差是否超过1，超过1返回-1，说明它不是平衡二叉树，非-1说明他是平衡二叉树。
2.代码：
public boolean isBalanced(TreeNode root) {
if(root==null){
return true;
}
//不等于-1说明是平衡树
return depth(root)!=-1;
}
//后续遍历获取二叉树的高度
public int depth(TreeNode root){
//递归终止条件
if(root==null){
return 0;
}
//左子树
int leftDepth = depth(root.left);
//左子树已经不是平衡树了，直接返回-1
if(leftDepth==-1){
return -1;
}
//右子树
int rightDepth = depth(root.right);
//右子树已经不是平衡树了，直接返回-1
if(rightDepth==-1){
return -1;
}
//左右子树高度差大于1，return -1表示已经不是平衡树了
if(Math.abs(leftDepth-rightDepth)>1){
return -1;
}
//返回当前树的高度,通过该返回值是否是-1来判断是否平衡树
return Math.max(leftDepth,rightDepth)+1;
}257. 二叉树的所有路径
题目链接 | 文档讲解 |视频讲解：链接
1.思路：
题意是给你一个二叉树的根节点 root ,按任意顺序 ，返回所有从根节点到叶子节点的路径。因为需要根节点到叶子节点,所以采用的是前序遍历。
2.代码：
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
if(root==null){
return res;
}
dfs(root,"",res);
return res;
}
public void dfs(TreeNode root,String str,List<String> result){
//递归终止条件
if(root==null){
return;
}
//递归终止条件,遍历到叶子节点
if(root.left==null&&root.right==null){
//记录当前节点的值,拼接字符串,添加到结果集
result.add(new StringBuilder().append(str).append(root.val).toString());
return;
}
//中序遍历,拼接字符串
String temp=new StringBuilder().append(str).append(root.val).append("->").toString();
//递归遍历左子树
dfs(root.left,temp,result);
//递归遍历右子树
dfs(root.right,temp,result);
}404.左叶子之和
题目链接 | 文档讲解 |视频讲解：链接
1.思路：
- 前序遍历
- 左叶子：节点的左孩子不为空，且左孩子的左孩子和右孩子都为空
2.代码：
public int sumOfLeftLeaves(TreeNode root) {
if(root==null){
return 0;
}
//遍历左子树
int leftCount =sumOfLeftLeaves(root.left);
//遍历右子树
int rightCount = sumOfLeftLeaves(root.right);
int result=0;
//判断左叶子节点
if(root.left!=null && root.left.left==null && root.left.right==null){
result= root.left.val;
}
return leftCount+rightCount+result;
}222.完全二叉树的节点个数
题目链接 | 文档讲解 |视频讲解：链接
1.思路：
当成普通二叉树去计算节点数，会遍历到每一个节点
2.代码：
public int countNodes(TreeNode root) {
//当成普通二叉树，求数量
if(root ==null){
return 0;
}
int leftNums =countNodes(root.left);
int rightNums=countNodes(root.right);
int result=leftNums+rightNums+1;
return result;
}1.思路：
完全二叉树：除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置
完全二叉树的特性去求 二叉树的节点公式：2^n-1 n指的是深度
如何判断是否是完全二叉树：一直向左遍历，一直向右遍历，判断左子树的深度和右子树的深度是一样的，这样不会遍历所有的节点
上图可知： 如果当前数不是完全二叉树，就去判断该节点的子节点是否是完全二叉树
2.代码
public int countNodes(TreeNode root) {
if(root==null){
return 0;
}
TreeNode left=root.left;
TreeNode right=root.right;
//用于记录左右子树的深度
int leftLength =0;
int rightLength =0;
while(left!=null){
left=left.left;
leftLength++;
}
while(right!=null){
right=right.right;
rightLength++;
}
if(leftLength==rightLength){
return (2 <<leftLength )-1;
}
//左
int llength=countNodes(root.left);
//右
int rlength=countNodes(root.right);
//中
return llength+rlength+1;
}