LeetCode-110. 平衡二叉树

问题地址

LeetCode每日一题/2020-08-17

LeetCode110. 平衡二叉树

问题描述

规则

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

示例1

给定二叉树 [3,9,20,null,null,15,7]

返回 true 。

示例2

给定二叉树 [1,2,2,3,3,null,null,4,4]

返回 false 。

解析

解题思路

高度平衡二叉树的定义：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。
– 如果一颗二叉树是高度平衡二叉树，那么它的所有子树也都是高度平衡二叉树。

根据给定规则我们可以利用递归来判断一颗树是否是高度平衡二叉树。

复杂度分析

时间复杂度，对于递归函数的时间复杂度，我们可以利用公式法来计算：

$T(n)= a×T(\frac{n}{b}) + f(n)$

公式中递归部分的时间复杂度是： $O(n^{log_{b}^a})$ ；
$f(n)$ 是每次递归完毕之后额外的计算执行时间，本例中每次计算完左右子树高度之后需要做+1处理，所以$f(n)=f(1)$；
故本例中 $T(n) = 2×T(\frac{n}{1}) + 1，a = 2，b = 1，f(n) = 1$ 带入公式得到 $O(n^{log_{1}^2})=O(n^2)$

空间复杂度，其中 $n$ 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 $n$ ，故空间复杂度为 $O(n)$ ；

定位问题

计算任意节点的所有子树是否满足高度平衡二叉树；

数据操作分析

比较左右子树高度差是否<=1；
分别判断root节点的左右子树是否是高度平衡子树；

编码实现

/**
 * LeetCode110
 */
public class BalancedBinaryTree {

    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);
        }

    }

    private int height(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        }
        return Math.max(height(treeNode.left), height(treeNode.right)) + 1;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

官方解法

自顶向下的递归

思路：
- 定义函数 $height$ ，用于计算二叉树中的任意一个节点 $p$ 的高度：

$height(p)= \begin{cases} 0 \\ max(height(p.left), height(p.right))+1 \\ \end{cases}$

有了计算节点高度的函数，即可判断二叉树是否平衡。具体做法类似于二叉树的前序遍历，即对于当前遍历到的节点，首先计算左右子树的高度，如果左右子树的高度差是否不超过 1，再分别递归地遍历左右子节点，并判断左子树和右子树是否平衡。这是一个自顶向下的递归的过程。

复杂度分析：
- 时间复杂度： $O(n^2)$ ，其中 $n$ 是二叉树中的节点个数。最坏情况下，二叉树是满二叉树，需要遍历二叉树中的所有节点，时间复杂度是 $O(n)$ 。对于节点 $p$ ，如果它的高度是 $d$ ，则 $height(p)$ 最多会被调用 $d$ 次（即遍历到它的每一个祖先节点时）。对于平均的情况，一棵树的高度 $h$ 满足 $O(h)=O(logn)$ ，因为 $d\leqh$ ，所以总时间复杂度为 $O(nlogn)$ 。对于最坏的情况，二叉树形成链式结构，高度为 $O(n)$ ，此时总时间复杂度为 $O(n^2)$ 。
- 空间复杂度： $O(n)$ ，其中 $n$ 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 $n$ 。

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;
        }
    }
}

自底向上的递归

思路：
方法一由于是自顶向下递归，因此对于同一个节点，函数 $height$ 会被重复调用，导致时间复杂度较高。如果使用自底向上的做法，则对于每个节点，函数 $height$ 只会被调用一次。
自底向上递归的做法类似于后序遍历，对于当前遍历到的节点，先递归地判断其左右子树是否平衡，再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的，则返回其高度（高度一定是非负整数），否则返回 -1。如果存在一棵子树不平衡，则整个二叉树一定不平衡。
复杂度分析：
- 时间复杂度： $O(n)$ ，其中 $n$ 是二叉树中的节点个数。使用自底向上的递归，每个节点的计算高度和判断是否平衡都只需要处理一次，最坏情况下需要遍历二叉树中的所有节点，因此时间复杂度是 $O(n)$ 。
- 空间复杂度： $O(n)$ ，其中 $n$ 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数，递归调用的层数不会超过 $n$ 。

class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}