【LeetCode 110.平衡二叉树】两种递归实现:自顶向下、自底向上

题目描述:给定一个二叉树,判断它是否是高度平衡的二叉树。

本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

解法 1: 自顶向下

根绝平衡二叉树的定义,可以递归比较每个节点的左右子树的高度差,是否超过 1。如果所有节点都满足条件,那么就是一棵平衡二叉树;否则,不是一棵平衡二叉树。

这里计算二叉树高度的思路在《LeetCode 104.二叉树的最大深度》中有介绍两种方法(递归、层序遍历),这里不再冗述。

代码实现如下:

// ac地址:https://leetcode-cn.com/problems/balanced-binary-tree/
// 原文地址:https://xxoo521.com/2020-03-23-balanced-tree
/**
 * 判断是否是平衡二叉树
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    if (!root) return true;
    return (
        isBalanced(root.left) &&
        isBalanced(root.right) &&
        Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1
    );
};

/**
 * 获取二叉树的高度
 * @param {TreeNode} root
 * @return {number}
 */
function maxDepth(root) {
    if (!root) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

解法 2: 自底向上(推荐)

你可能已经发现解法 1 的问题了:每个节点的高度值都会被重复计算。这带来了额外的时间消耗。那么如何避免这些重复计算呢?

解决思路是:先计算左右子树是否是平衡二叉树,并且计算、保存左右子树的高度,那么当前二叉树的高度可以通过左右子树的高度直接计算出来。

在 JavaScript 中,想要保存过程中的计算结果非常简单:可以通过传递一个对象作为参数,其上有属性 depth,表示以当前节点为根节点的二叉树的高度。

代码实现如下:

// ac地址:https://leetcode-cn.com/problems/balanced-binary-tree/
// 原文地址:https://xxoo521.com/2020-03-23-balanced-tree
/**
 * @param {TreeNode} root
 * @param {Object} obj
 * @return {boolean}
 */
var isBalanced = function(root, obj = {}) {
    if (!root) {
        obj.depth = 0;
        return true;
    }

    const left = {}; // 左子树信息
    const right = {}; // 右子树信息
    if (isBalanced(root.left, left) && isBalanced(root.right, right)) {
        if (Math.abs(left.depth - right.depth) > 1) {
            // 检查左右子树高度差
            return false;
        }

        obj.depth = Math.max(left.depth, right.depth) + 1; // 当前二叉树的高度
        return true;
    } else {
        return false;
    }
};

更多资料

整理不易,若对您有帮助,请给个「关注+点赞」,您的支持是我更新的动力 👇

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×