110. 平衡二叉树

平衡二叉树

原题：

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

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

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

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

提示：

• 树中的节点数在范围 [0, 5000] 内
• -104 <= Node.val <= 104

解题方法：

解法一：

class Solution {
public:      //计算每个节点左右子树的深度，如果有一个结点左右子树深度差大于1则返回false
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        return (abs(depth(root->left)-depth(root->right))<=1)&&isBalanced(root->left)&&isBalanced(root->right);
    }

    int depth(TreeNode* root)
    {
        if(!root) return 0;
        int L=depth(root->left);
        int R=depth(root->right);
        return max(L,R)+1;
    }
};

解法二（自底向上的递归）：

class Solution {
public:      //计算每个节点左右子树的深度，如果有一个结点左右子树深度差大于1则返回false
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        return (depth(root)!=-1);
    }

    int depth(TreeNode* root)
    {
        if(!root) return 0;
        int L=depth(root->left);
        int R=depth(root->right);
        return ((R!=-1)&&(L!=-1)&&abs(L-R)<2)?max(L,R)+1:-1;
    }
};

做题小结：

针对解法一：

1. 这种解法是我自己想出来的，即对每一结点，求其左右的深度，然后左右深度之差只要大于1了，就返回false。但这种解法空间复杂度虽然比较低，但是时间复杂度太高，达到了O(n^2)，因此需要优化（这么写是拿不到offer的！！）
2. 在官网解法看到了这种解法名为自顶向下的递归解法

针对解法二：

1. 解法二使用的方法其实像后序遍历，从子节点开始检查以子节点为根的树是否为平衡树，如果有一个子节点为根的树不为平衡树，那么整棵树就不是平衡树，就可以直接返回，免去了依次检测的必要
2. 可以在return时活用&&，免去使用if的必要，来加快速度