LeetCode 110. 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 depth of the two subtrees of every node never differ by more than 1.

翻譯

給一個二元樹，判斷這是不是一個高度平衡的樹。

在這個問題中，高度平衡樹的定義是一個樹兩個子樹每個node的level不能差超過1。

範例：

高度平衡樹
     1
   /   \
  2     5
 / \     \
3   4     6  

在節點5的時候，節點5左子樹level = 1，右子樹level = 3， 3-1 > 1 因此這是非高度平衡樹
     1
   /   \
  2     5
 / \     \
3   4     6  
           \
            7 

思路

1. 這題會用到之前寫過的LeetCode 104. Maximum Depth of Binary Tree
2. 尋找node左樹的深度與右樹的深樹後相減，如果差超過1，表示非高度平衡樹
3. 如果沒差超過1，傳入左節點與右節點繼續判斷是否為高度平衡樹

解題

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isBalanced = function(root) {
    if(root == null || (root.right == null && root.left == null)) return true;

    // 找出左樹，右樹的深度
    var dL = findDeep(root.left);
    var dR = findDeep(root.right);

    // 深度是否差1內
    var diff = Math.abs(dL-dR) <= 1;

    //如果深度差超過1, return false
    //深度沒差超過1，傳入左右節點繼續判斷
    return diff && isBalanced(root.left) && isBalanced(root.right);

};

// 找出節點深度
function findDeep(root){
    if(root == null) {
        return 0;
    }
    var deepL = 1+findDeep(root.left);
    var deepR = 1+findDeep(root.right);

    return deepL > deepR ? deepL:deepR;
}