平衡二叉树，力扣

目录

前序遍历与后续遍历

题目地址：

题目：

我们直接看题解吧：

审题目+事例+提示：

解题方法：

难度分析：

解题方法分析：

解题分析：

解题思路：

代码实现：

补充说明：

代码进一步优化：

代码实现（自顶向下） ：

---

前序遍历与后序遍历

下面方法需要用，大家不太熟或者想加强一下可以先刷一下

二叉树的前序遍历，力扣-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;
        }
    }
}