平衡二叉树 🌟🌟🌟🌟🌟简单

算法系统课免费

课后作业

问题描述

原文链接：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

代码实现

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // n!
    // 优化版本
    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        if(maxDexth(root) == -1){
            return false;
        }
        return true;

    }

    int maxDexth(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = maxDexth(root.left);
        if(left == -1){
            return -1;
        }
        int right = maxDexth(root.right);
        if(right == -1){
            return -1;
        }

        if(Math.abs(left - right) > 1){
            return  -1;
        }

        return 1 + Math.max(left, right);
    }
}

Python

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True

        if self.maxDepth(root) == -1:
            return False

        return True

    def maxDepth(self, root):
        if not root:
            return 0

        left = self.maxDepth(root.left)
        if left == -1:
            return -1

        right = self.maxDepth(root.right)
        if right == -1:
            return -1

        if abs(left - right) > 1:
            return -1

        return 1 + max(left, right)

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if (!root) {
            return true;
        }

        if (maxDepth(root) == -1) {
            return false;
        }

        return true;
    }

    int maxDepth(TreeNode* root) {
        if (!root) {
            return 0;
        }

        int left = maxDepth(root->left);
        if (left == -1) {
            return -1;
        }

        int right = maxDepth(root->right);
        if (right == -1) {
            return -1;
        }

        if (abs(left - right) > 1) {
            return -1;
        }

        return 1 + max(left, right);
    }
};

发表回复取消回复

后才能评论

泡芙永久会员 2023年9月22日上午11:27

先序遍历 + 判断深度（从顶至底）

Time：O(n^2)，最好情况下（为“满二叉树”），每层执行复杂度× 层数复杂度=O(n × logn)。但最坏情况下（退化成链表）,高度为O(n)，时间复杂度为O(n^2)
Space：最差情况下（当树退化为链表时），递归深度可达到 n

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }

        // 当前子树、当前子树的左子树、当前子树的右子树 是否是平衡树
        return Math.abs(maxDeaxth(root.left) - maxDeaxth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    int maxDeaxth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return 1 + Math.max(maxDeaxth(root.left), maxDeaxth(root.right));
    }
}

后序遍历 + 剪枝（从底至顶）

Time：O(n)，N 为树的节点数量，计算树的深度需要遍历所有节点
Space：O(n)，最差情况下（当树退化为链表时），递归深度可达到 n

class Solution {
    public boolean isBalanced(TreeNode root) {
        return maxDeaxth(root) != -1;
    }

    int maxDeaxth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = maxDeaxth(root.left);
        int right = maxDeaxth(root.right);

        if (left == -1 || right == -1 ||Math.abs(left - right) > 1) {
            return -1;
        }

        return 1 + Math.max(left, right);
    }
}

阿尚普通 2023年8月21日上午10:45

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;

        return check(root) == -1 ? false : true;
    }

    public int check(TreeNode root){
        if(root == null) return 0;

        int left = check(root.left);
        if(left == -1) return left;
        int right = check(root.right);
        if(right == -1) return right;

        //判断左右子树高度差是否超过1
        if(Math.abs(left - right) > 1){
            return -1;
        }

        return Math.max(left, right) + 1;
    }
}

帅气的冬瓜普通 2023年7月5日下午5:45

打卡

登录以回复

课后作业

问题描述

代码实现

Java

Python

C++

发表回复 取消回复

评论(3)

先序遍历 + 判断深度 （从顶至底）

后序遍历 + 剪枝 （从底至顶）

付款后无法显示下载地址或者无法查看内容？

发表回复取消回复

先序遍历 + 判断深度（从顶至底）

后序遍历 + 剪枝（从底至顶）