目录
前序遍历与后续遍历
题目地址：
题目：
我们直接看题解吧：
审题目+事例+提示：
解题方法：
难度分析：
解题方法分析：
解题分析：
解题思路：
代码实现：
补充说明：
代码进一步优化：
代码实现（自顶向下） ：
前序遍历与后序遍历
下面方法需要用，大家不太熟或者想加强一下可以先刷一下
二叉树的前序遍历，力扣-CSDN博客
二叉树的后序遍历，力扣-CSDN博客
题目地址：
110. 平衡二叉树 - 力扣（LeetCode）
难度：简单
乍一看以为有点难，其实仔细理解一下，发现还行，大家可以简单看一下解题思路，然后再照着代码看，会更容易理解一些。
今天刷平衡二叉树，大家有兴趣可以点上面链接，看看题目要求，试着做一下。
题目：
给定一个二叉树，判断它是否是高度平衡的二叉树。
注：本题高度平衡二叉树定义为一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1
我们直接看题解吧：
审题目+事例+提示：
平衡二叉树的定义：
二叉树的每个节点的左右子树的高度差的绝对值不超过1。
注：空树也可以作为平衡二叉树
性质：当前树的深度等于左子树深度与右子树的深度中的最大值+1
解题方法：
根据定义可知，一棵若为平衡二叉树，当且仅当其所右子树也都是平衡二叉树，
因此可以用递归的方法。
方法1、自顶向下递归
方法2、自底向上递归
难度分析：
主要考察树及二叉树的相关基础，对于初学者来说，方法2需要打破思维限制可能难一点。
解题方法分析：
方法1，我们可能比较容易想得到，但是它不是最优的。
简单说一下思路：
具体做法类似于二叉树的前序遍历，即对于当前遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差是否不超过 1，再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡。
这是一个自顶向下的递归的过程。它最大的问题是会产生重复计算，对于同一个节点，用于计算二叉树高度的函数 height(） 会被重复调用，导致时间复杂度较高。
但如果使用自底向上的做法，则对于每个节点，函数 height(） 只会被调用一次，因此，下面着重讲一下方法2.
解题分析：
自底向上递归的做法类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回−1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。
解题思路：
1、在函数isBalanced()中,调用height()参数为树根节点root，若最终返回值>=0，则说明此树平衡，即返回true，反之返回false。
2、创建用于计算二叉树高度的函数height(root)
·判断根节点是否为空，空则返回0
·分别递归调用函数height()获取当前节点左右子树的高度
`判断其左右子树高度是否为-1，或者左右子树绝对值之差大于1，满足则返回-1
若不满足，则返回其左右子树最大值+1
代码实现：
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) >= 0;//若最终返回值不等于-1，则说明此树平衡，即返回true，反之返回
// false。
}
public int height(TreeNode root) {//创建用于计算二叉树高度的函数height(root)
if (root == null) {
return 0; //判断根节点是否为空，空则返回0
}
int leftHeight = height(root.left);//递归调用函数height()获取当前节点左子树的高度
int rightHeight = height(root.right);//递归调用函数height()获取当前节点右子树的高度
if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) { //判断其左右子树高度是否为-1，或者左右子树绝对值之差大于1
return -1; //满足则返回-1
} else {//若不满足，则返回其左右子树最大值+1
return Math.max(leftHeight, rightHeight) + 1;
}
}
}
补充说明：
第一次调用函数时，若根节点为空，则整棵树为空树了
代码进一步优化：
如果左子树已经返回-1了就不需要再递归右子树了，直接返回-1
class Solution {
public boolean isBalanced(TreeNode root) {
return balanced(root) != -1;
}
private int balanced(TreeNode node) {
if (node == null) return 0;
int leftHeight, rightHeight;
if ((leftHeight = balanced(node.left)) == -1
//如果左子树已经返回-1了就不需要再递归右子树了，直接返回-1
|| (rightHeight = balanced(node.right)) == -1
|| Math.abs(leftHeight - rightHeight) > 1)
return -1;
return Math.max(leftHeight, rightHeight) + 1;
}
}
代码实现（自顶向下） ：
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
} else {
return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
}
public int height(TreeNode root) {
if (root == null) {
return 0;
} else {
return Math.max(height(root.left), height(root.right)) + 1;
}
}
}
好文推荐
发表评论