110. Balanced Binary Tree

Leetcode

https://leetcode.com/problems/balanced-binary-tree/

題目

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Example 3:

Input: root = []
Output: true

解答

• 方法一

Top-down recursion

創建一個 getHeight 的 function 幫助取得高度

const getHeight = function(node) {
    if (!node) return 0;

    const leftH = getHeight(node.left);
    const rightH = getHeight(node.right);

    return Math.max(leftH, rightH) + 1;
};

var isBalanced = function(root) {
    if (!root) return true;
    
    const leftH = getHeight(root.left);
    const rightH = getHeight(root.right);
    
    return Math.abs(leftH - rightH) <= 1 && isBalanced(root.left) && isBalanced(root.right);
};

Runtime: 97 ms, faster than 64.27% of JavaScript online submissions for Balanced Binary Tree.

Memory Usage: 46.9 MB, less than 79.06% of JavaScript online submissions for Balanced Binary Tree.

• 方法二

Bottom-up recursion

方法一有個缺點是從上而下算的 getHeight 到下層子節點時又會被重新計算，所以方法二使用 bottom-up 方法計算高度，並將每個子節點的高度記錄下來避免重複計算高度

const helper = (node) => {
    if (!node) return [true, 0];
    
    const [isLeftBalanced, leftH] = helper(node.left);
    if (!isLeftBalanced) return [false, 0];
    
    const [isRightBalanced, rightH] = helper(node.right);
    if (!isRightBalanced) return [false, 0];
    
    return [Math.abs(leftH - rightH) <= 1, Math.max(leftH, rightH) + 1] 
}

var isBalanced = function(root) {
    return helper(root)[0];
};

Runtime: 90 ms, faster than 72.49% of JavaScript online submissions for Balanced Binary Tree.

Memory Usage: 49.4 MB, less than 7.67% of JavaScript online submissions for Balanced Binary Tree.