LeetCode（剑指 Offer）- 55 - II. 平衡二叉树

题目链接：点击打开链接

题目大意：略

解题思路：略

相关企业

• 字节跳动
• Facebook
• 谷歌（Google）
• 苹果（Apple）
• 亚马逊（Amazon）
• 微软（Microsoft）
• 美团
• 猿辅导
• SAP 思爱普
• 阿里巴巴
• 抖音

AC 代码

• Java

 
// 解决方案(1)
class Solution {
 
    boolean res = true;
 
    public boolean isBalanced(TreeNode root) {
        dfs(root);
        return res;
    }
 
    int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
 
        int l = dfs(node.left) + 1;
        int r = dfs(node.right) + 1;
        if (Math.abs(l - r) > 1) {
            res = false;
        }
 
        return Math.max(l, r);
    }
}
 
// 解决方案(2)
class Solution {
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }
 
    private int recur(TreeNode root) {
        if (root == null) return 0;
        int left = recur(root.left);
        if(left == -1) return -1;
        int right = recur(root.right);
        if(right == -1) return -1;
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
}
 
// 解决方案(3)
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
 
    private int depth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
}

• C++

 
// 解决方案(1)
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return recur(root) != -1;
    }
private:
    int recur(TreeNode* root) {
        if (root == nullptr) return 0;
        int left = recur(root->left);
        if(left == -1) return -1;
        int right = recur(root->right);
        if(right == -1) return -1;
        return abs(left - right) < 2 ? max(left, right) + 1 : -1;
    }
};
 
// 解决方案(2)
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if (root == nullptr) return true;
        return abs(depth(root->left) - depth(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
    }
private:
    int depth(TreeNode* root) {
        if (root == nullptr) return 0;
        return max(depth(root->left), depth(root->right)) + 1;
    }
};